Does Paxos consensus algorithm scale linearly? I'm trying to build a P2P web application using Paxos to obtain a consensus value.

How well does Paxos scale? linearly? or what kind of distribution can you expect? E.g. in using 10 to 10,000 users in the network.

If not, are there consensus algorithms that scale well?

Apologies if this answer does not belong to this site

According to this paper released in 2013 which compares the performance over scale of Paxos and an optimized version of it Fast Paxos

  Paxos and Fast Paxos are optimal consensus algorithms that are simple and elegant, while suitable for efficient implementation

Reading further section 3.4. Scale Up , you can find two graph plots.

The left plot shows the number of requests served on y-axis and the number of replicas on x-axis.
The right plot displays the average response time on y-axis and the number of replicas on x-axis.

I think it gives an idea about what one should expect.They are optimal choices according to the paper and I don't know of any other

As far as it goes for the running time , I think I read somewhere that it's linear.


Why would this Semidefinite Program be Dual Infeasible? My semidefinite program amounts to two constraints, $L_1 = 0$ and $L_2 = 0$ where $L_i$ are linear functions of my variables $x_{ij}$ with the additional constraint that the $x_{ij}$ matrix is positive semidefinite. I see no way that this program would be infeasible, because just setting every variable to 0 would satisfy all the constraints.

I have written the semidefinite program according to SPDA format. In this format, my SDP is the dual program. When I solve it with the software csdp, it tells me that the "dual program is infeasible."

Here is the particular SDP:

2
1
11
0.0 0.0
0 1 1 10 1.0
1 1 1 10 .25
1 1 3 10 .25
1 1 6 10 -.25
1 1 8 10 -.25
1 1 9 10 -.5
2 1 2 11 -3.0
2 1 3 11 -4.0
2 1 4 11 1.0
2 1 5 11 1.0
2 1 6 11 -4.0
2 1 7 11 3.0
2 1 9 11 1.0

csdp outputs This is a pure dual feasibility problem.
Iter:  0 Ap: 0.00e+000 Pobj:  0.0000000e+000 Ad: 0.00e+000 Dobj:  0.0000000e+000
Iter:  1 Ap: 1.00e+000 Pobj:  5.6521881e+000 Ad: 9.00e-001 Dobj:  0.0000000e+000
Declaring dual infeasibility.
Success: SDP is dual infeasible
Certificate of dual infeasibility: tr(CX)=1.00000e+000, ||A(X)||=1.38778e-017
`

The original poster seems to misunderstand the distinction between "primal infeasible" and "dual infeasible."

The output from CSDP shows that the problem is primal feasible ($X=0$ is a primal feasible solution) but that the primal problem is unbounded. By weak duality, the corresponding dual problem is infeasible.

If you just want a primal feasible solution and don't care about the primal objective value, then you can get this in a couple of ways:

You can use the "certificate" returned by CSDP.  This is a matrix $X$ such that $X$ is positive semidefinite and $A(X)=0$.  Any positive multiple of this matrix is a primal feasible solution to your SDP.
You can add an additional constraint that causes the objective function to be bounded.  A simple choice would be trace(X)=100.

By the way, it's easy to confirm this using another SDP solver such as SeDuMi or SDPT3 or SDPA.


How is CLR(1) grammar more powerful than LALR(1) grammar I am unable to understand how Canonical LR(1) grammar is more powerful than LookAhead LR(1). Both have lookahead symbols in their items and works almost similarly, so how can CLR(1) derive a larger set of languages than LALR(1).

LALR(1) is the grammar obtained by merging states of CLR(1). The states with the exact same production rules i.e. the exact same core, but different lookahead are combined together.
Specifically, consider
$$I_i: A\rightarrow \alpha \bullet \beta, \; a \;\; \mbox{and}\;\; I_j: A\rightarrow \alpha \bullet \beta, \; b$$
The merged state looks like
$$I_{ij}: A\rightarrow \alpha \bullet \beta, \; a/b$$
This merging introduces reduce-reduce conflict, even if the original LR(1) grammar was free of such conflicts. To show this, we will consider an example.
Let there be two states $I_i$ and $I_j$ in the LR(1) grammar.
$I_i:$

$A\rightarrow \alpha \bullet, \; p$
$B\rightarrow \alpha \bullet, \; q$

and $I_j:$

$A\rightarrow \alpha \bullet, \; r$
$B\rightarrow \alpha \bullet, \; s$

The merged state $I_{ij}$ is

$A\rightarrow \alpha \bullet, \; p/r$
$B\rightarrow \alpha \bullet, \; q/s$

Now, for the LALR(1) grammar to have a reduce-reduce conflict either

$p=s$ which is possible without a reduce-reduce conflict in $I_i$ and $I_j$ OR
$q=r$ which is also possible without a reduce-reduce conflict in $I_i$ and $I_j$

Thus, it proves why LALR(1) is less powerful than CLR(1).


Is Q-Learning ever better than Brute Force? I am currently learning about the Q-learning algorithm, so I therefore assume that it has some use or purpose. However I currently cannot see how it is in any way useful. In terms of complexity class, it appears to perform equal to or worse than brute force, which as far as I am aware, is the lowest you ever need to go to compute something computable.

What, if anything, have I missed?

Reinforcement Learning (RL) algorithms are useful in a setting when the structure of the environment is unknown and/or stochastic. The environment is normally formalized as a Markov Decision Process (MDP) or Partially Observable Markov Decision Process (POMDP) and the goal of an RL agent is then to maximize its cumulative reward (or minimize its regret with respect to the best alternate policy) while behaving in the environment.

As such it isn't clear how a brute force algorithm would efficiently deal with the stochastic nature of the environment or the fact that this procedure is almost universally assumed to be done online. For more information and a modern overview of RL I recommend this excellent reference by Csaba Szepesvari.


Does mutual exclusion hold in this case? I entered into a discussion with a friend on the following question, which asks if mutual exclusion holds:
Consider two processes:

$s_1$ and $s_2$ are two variables, set equal initially.
P1:

while $s_1 = s_2$: wait.

/execute critical section/

$s_1$ is set such that it is not equal to $s_2$

P2:

while $s_1 = s_2$: wait.

/execute critical section/

$s_1$ is set such that it is not equal to $s_2$

My friend argues that mutual exclusion holds. His explanation:

Mutual Exclusion holds if the following implication holds:
If a process is in its critical section, then other processes should not be allowed in their critical sections.

Consider this implication as $P \to Q$. He argues that since the premise $P$ is wrong (because none of P1 and P2 are in their critical sections), the implication is true and hence mutual exclusion holds.
Whereas my thinking is that when none of the processes get to enter their critical section, talking about mutual exclusion is pointless and hence the property doesn't hold.
Is the implication way of thinking the correct approach? I feel that it's not, but I have not been able to prove my intuition.

Your friend is correct. In your context, mutual exclusion holds if at most one process is at a critical section at any given time.

You state that you feel that this interpretation is wrong, but you have not been able to prove your intuition. You cannot prove a definition! What you are really saying is that the concept of mutual exclusion is vacuous if no process is ever in a critical section. To some extent you are correct—this agrees with colloquial usage. The same colloquial usage also states that "A or B" has the connotation of "A or B, but not both". When dealing with formal concepts you have to forgo the colloquial point of view, trading it with the mathematical point of view.


Loop termination - Loop invariant (x >= 0 && y >= 0)
q = 0;
r = x;
while ( r >=y ) {
  r = r - y;
  q = q + 1;
}
(x = q*y +r) && (r >= 0) && (r < y)

For this what if y = 0 ?

If y = 0, then r stays at r inside the while loop, which makes r >= y true always. So it doesn't seem to terminate.

So I think, for pre-condition, doesn't it have to be (y > 0) to make sure this program terminates ?

As mentioned in the comments, it depends on whether you care about partial correctness or total correctness.

Partial correctness requires that, if the program starts from any state satisfying the preconditions, and if the program terminates in a final state, then such final state satisfies the postcondition.

Total correctness requires that, if the program starts from any state satisfying the preconditions, then the program terminates in a final state, which satisfies the postcondition.

Only total correctness requires termination, partial correctness does not.

The Hoare logic rules for program statements are roughly the same, except for while loops. In partial correctness, the while rule requires to find a suitable invariant property. In total correctness, the rule requires both the invariant property and the variant: this is a strictly decreasing, natural valued function of the state (roughly, providing an upper bound on the number of loops).

If your rules have no variant, but only deal with the invariant, they are meant to be used to prove partial correctness, only.


Is spectral radius of a graph related to its radius? I am searching for algorithms to estimate the radius of a graph, and I found out that there are papers about the spectral radius of a graph. As far as I know, the radius of a graph is $\min_{v \in V} ecc(v)$ where $ecc(v)$ is the depth of a tree rooted at $v$, and the spectral radius of a graph is the largest eigenvalue of its adjacency matrix. Are these two concepts related in some way?

No, the two notions are unrelated. To see this, we construct a pair of graphs with the same spectrum, but different radius. Graphs that have the same spectrum are called co-spectral. There exist non-isomorphic graphs that have the same spectrum.

This page  shows two co-spectral graphs with different radius: the 4-cycle and point has infinite radius, as it is disconnected, but the co-spectral 4-star has radius 1.

The other way around, two graphs of the same radius with a different spectrum, isn't hard to see either. Simply take two graphs with a different number of nodes  and the same radius, their spectra must differ as their adjacency matrices have different size.

The word radius is quite general, so it is no surprise to see it in two unrelated terms.


How to prove a complete binary tree of depth N has $2^{N+1} - 1$ nodes? Here is the description of a proof problem:

A complete binary tree of depth N is a binary tree in which every node on levels $0,1,2,...,N-1$ is a parent and has two children, and each node on level N is a leaf.

It's asking for proving binary tree of depth N has $2^{N+1} - 1$ nodes.

I am not really sure how to approach this proof. I tried to plug in some values in $D(N) = 2^{N+1} - 1$ just to play with the formula, I get $D(1) = 2^{1+1} - 1 = 3$,  $D(2) = 2^{2+1} - 1 = 7$, $D(3) = 2^{3+1} - 1 = 15$, and so on. I still did not see how these numbers relate to the descriptions given and how I would relate these values to given facts to build a proof.

Hint 1: Draw some binary trees of depth $0, 1, 2$ and $3$. Depth $0$ is only the the root.

Hint 2: Use Induction on the depth of the tree to derive a proof.

The base case is depth $n=0$. With depth $0$ we only have the root, that is, $2^{0 + 1} - 1 = 1$ nodes, so the formula is valid for $n=0$.

The next case is depth $n=0+1=1$, since the tree is full the root must have $2$ leafs. So we have $1 + 2 = 3$ nodes in total. The formula still holds since $2^{1+1} - 1 = 3$.

Can you generalize this procedure? Does this hold for all $n \geq 0$?


Finding a simple cycle that goes through two vertices Given a directed graph $G$ and two vertices $u$ and $w$, how can we find a simple cycle that goes through $u$ and $w$?

One can try putting together paths from $u$ to $w$ and $w$ to $u$ — but these might have edges or nodes in common, even if they are chosen to be shortest paths.

The decision version of your problem (deciding whether such a cycle exists) is NP-complete. See Proposition 9.2.1(P3) on page 477 (495) in Digraphs – Theory, Algorithms and Applications by Bang-Jensen and Gutin.


Generating a Context Free Grammar from a Language I am wondering how to go from a language such as this:

L = {a^n b^m c^k | n = m or m != k}

To a Context Free Grammar. I know that I would have to turn it into two separate languages but I don't know how to create the production rules for each of those languages.

Given $L=\{a^nb^mc^k | \ n=m \ \vee m \neq k \}$ you can see it as $L=L_1 \cup L_2$ where:

$L_1=\{a^nb^mc^k | \ n=m\}$
$L_2=\{a^nb^mc^k | \ m \neq k\}$

Then you define 2 Context free grammars $G_1$ and $G_2$ for the 2 languages and in order to express the OR condition your add the production rule

$S \rightarrow S_1\ | \ S_2$

where $S$ is the starting symbol for $G$, $S_1$ for $G_1$ and $S_2$ for $G_2$.

As suggested in the comments, $L_1$ and $L_2$ can be splitted in order to make it easier the design of the grammars.

$L_1=L_{1,1} \cdot L_{1,2}$ where:

$L_{1,1}=\{ a^nb^n | \ n \geq 0 \ \}$
$L_{1,2}=\{ c^k | \ k \geq 0\ \}$

$L_2=L_{2,1} \cdot (L_{2,2} \vee L_{2,3})$ where:

$L_{2,1}=\{a^n \ | \ n \geq 0\}$
$L_{2,2}=\{b^mc^k | \ m < k\}$
$L_{2,3}=\{b^mc^k | \ m > k\}$


Calculate number of cache lines per set or cache size How can I calculate the number of cache lines per set or the cache size with the given information?

m (number of physical address bits): 32
C (cache size): unknown
B (Block size in bytes): 32
E (number of lines per set): unknown
S (number of cache sets): 32
t (tag bits): 22
s (set index bits): 5
b (block offset bits): 5
associativity unknown

Since we can calculate C with C=B*E*S or E with E=C/(B*S). I just need to know how to calculate C or E.

You can calculate it with the help of tag, index, and offset bits. Read about it here.


Why can't we replace Dijkstra's priority queue with a regular queue? I am confused why we can't simply use a normal queue instead of a priority queue for Dijkstra's. I agree that you can find the shortest path in fewer iterations of the while loop using a priority queue. However, the runtime will still be O((E + V) log V). However, with a queue, that runtime will be O(E + V). Can anybody find a simple example of where Dijkstra's would fail if we used a queue instead of a Priority Queue?

The whole point of Dijkstra is that you visit the nodes in order of their distance from the source. If you use a queue that isn't a priority queue, then you visit the nodes in whatever "random" order the implementation happens to enqueue them.


From in-order representation to binary tree Is there a way to reconstruct a binary tree just from its in-order representation?

I've searched the internet, but I could only find solutions for reconstructing a binary tree from inorder and preorder representations, but none for only inorder.

The in-order traversal is not unique. The above trees have the same sequence 1,2,3,4,5. (They are isomorphic, but I assumed you consider ordered binary trees.)


Proof for time complexity of Insertion (k-proximate) Sort equals O(nk) The following is the definition for Proximate Sorting given in my paper:
An array of distinct integers is k-proximate if every integer of the array is at most k places away
from its place in the array after being sorted, i.e., if the $i$th integer of the unsorted input array is the
$j$th largest integer contained in the array, then $|i − j| ≤ k$.
The following is the proof for time complexity of k-proximate insertion sort:
To prove $O(nk)$, we show that each of the n insertion sort rounds swap an
item left by at most $O(k)$.
In the original ordering, entries that are $≥ 2k$ slots apart must already be ordered
correctly: indeed, if $A[s] > A[t]$ but $t − s ≥ 2k$, there is no way to reverse the
order of these two items while moving each at most $k$ slots. This means that for
each entry $A[i]$ in the original order, fewer than $2k$ of the items $A[0], . . . , A[i−1]$
are less than $A[i]$. Thus, on round $i$ of insertion sort when $A[i]$ is swapped into
place, fewer than $2k$ swaps are required, so round $i$ requires $O(k)$ time.
My problem with the proof is this line : "This means that for each entry A[i] in the original order, fewer than 2k of the items $A[0], . . . , A[i−1]$ are less than A[i]". The preceding statements just proved that $t-s < 2k$, otherwise the elements are sorted (as elements with distance greater than $2k$ cannot be swapped.) Isn't the correct statement : "This means that for each entry A[i] in the original order, fewer than 2k of the items $A[0], . . . , A[i−1]$ are greater than A[i]"?

Yes if you sort the array in ascending order you are right it should be less than $2k$ elements in $A[0],...,A[i-1]$ are greater than $A[i]$. A simple array were the statement w is wrong  ($k = 1$):
$$[1,2,3,4]$$
However is you sort in descending order it's the other way around.
But you have a good point because this seems to imply that ascending is meant...

"indeed, if A[s] > A[t] but t − s ≥ 2k, there is no way to reverse the order of these two items"


Non-deterministic logarithmic time complexity class Is that true that $Time(O(log(n)))=NTime(O(log(n)))$ iff $P=NP$?
It seems to me to be true, as I only need to take log on both sides, since log of a polynomial is $O(\log(n))$, but I don't know how to derive a proof from this intuition.

$\mathsf{DLOGTIME\subsetneq NLOGTIME}$. Search in unsorted array is a problem from $\mathsf{NLOGTIME}$, but it can't be solved deterministically in logarithmic time. This is proven. I also think that $\mathsf{NLOGTIME\not\subset DTIME}(o(n))$.

Padding argument here do not have an implication for $\mathsf P$ vs. $\mathsf{NP}$.


Is unary machine code a concept? Please assume for the sake of this session that humans can fluently read and understand machine languages and time isn't a problem in that regard.
I, not a computer scientist, would at least theorize that a unary machine language is possible but might just be much "less comfortable" than binary machine language.
Is unary machine code a concept?

Yes, you could express machine code in unary.  How do I know?  Well, anything that can be represented in binary, can be represented in unary.  Machine code can be represented in binary (as a binary string of bits)... therefore it can be represented in unary (as a unary string).
It wouldn't be useful or practical to do so.  It's not just less comfortable; it's much worse than that.  Conversion to unary involves an exponential increase in size (a string that takes $n$ bits in binary would take $2^n$ symbols in unary), so it would be totally infeasible in practice.  But in theory, you can imagine it; there's no barrier in principle.


A containment result in complexity A question on the interesting result in http://arxiv.org/pdf/1110.6126v1.pdf

It is shown $\Pi_2^P \not\subset P^{NP}$. But http://en.wikipedia.org/wiki/Polynomial_hierarchy says $\Pi_2^P = CoNP^{NP}$.

Does this mean an oracle in NP under which $P$ is not $CoNP$ has been shown?

Could someone elaborate?

Aaronson's result shows that $\Pi_2 \not\subset P^{N\!P}$ relative to a random oracle with probability 1. As he mentions, it had already been known that $N\! P != \mathrm{co}N\! P$ (and so $P \neq N\!P$ and $P \neq \mathrm{co}N\!P$) relative to a random oracle with probability 1: see the paper by Bennett and Gill. An oracle with respect to which $P \neq N\!P$ (and so $P \neq \mathrm{co}N\!P$) had been constructed earlier by Baker, Gill and Solovay. The construction is standard, and you can find many references online.


PDA pushing nothing given an input and the current stack top If we had a language $$\sum = \{a,b,c\}$$
for a pushdown automata, and the transition
$$a;A/AA$$
means "If you read in an a and A is at the top of the stack, push A", then would you be able to push nothing if you encounter an a and A is at the top of the stack with the transition:
$$a;A/\epsilon \space C$$
I am new to this notation so I am unsure of if I am doing it correctly.

In a commonly used model for pushdown atomata instructions of the automaton are of the form $(p,a,A,q,\alpha)$ meaning in state $p$, read $a$ from the input, pop $A$ from the stack, change to state $q$ and push $\alpha$ to the stack. In a diagram for the pda this can be represented as an edge from $p$ to $q$ labelled by $a; A/\alpha$. Note the first symbol of $\alpha$ end at the top of the stack.

There are some complications. First $a$ can be the empty string, so that the automaton ignores the letter on its input tape. To the contrary, the automaton cannot easily ignore its stack. The topmost symbol is always popped.

So if we want to perform the instruction "read $a$ whatever is on the stack" this is implemented as a set of instructions $(p,a,A,q,A)$ for all stack symbols $A$. If we want to perform "read $a$ when $A$ is on the stack (and leave $A$ there)" we just have the instruction $(p,a,A,q,A)$ for this particular symbol $A$. This seems to be your case.

Also the instruction "read $a$ and pop $A$" is then $(p,a,A,q,\varepsilon)$, pushing nothing after popping $A$.

Finally, the fact that we always need to pop at least one symbol means that formally the automaton cannot move on the empty stack, and blocks. This means if it did not just accept its input, it cannot continue and the computation fails.
(Be aware, not all books agree on the precise details here.)


Quickly determine if insertion sort or quick sort is better I'm in a scenario where ~30% of the time, my array is almost completely sorted, and the other 70% of the time, it is basically completely random. I want to quickly determine if my list is almost sorted, use insertion sort if it is, or quicksort otherwise. I've been searching this up all day but no luck.
The alternative solution is to shuffle the array and use quicksort every time, but this passes up on the opportunity to do 30% of the sorts faster.
The way I thought of is to compare consecutive terms, find the number of consecutive pairs out of order, and use that to estimate the entire array, but its not very reliable.
This seems like a common problem, so I was wondering what the "official" solution(s) is.

Quicksort is better unless the number of items in the wrong place is O(log n) only. There is a simple sorting algorithm that runs in O (n) if the number of items in the wrong place is a bit less than O (n / log n): Scan the array, and whenever two items are out of order put them into a separate array. Sort the separate array with Quicksort, then merge both arrays.
This will be not O(n), but faster than Quicksort, if the number of items in the wrong place is much lower than n, say O (n / sqrt(log(n)). The scanning + merging is obviously O(n). If t items are in the wrong order, then sorting them using Quicksort takes O (t log t), so it's O(n) in total if (t log t) = O(n), and asymptotically faster than Quicksort if t = o(n).


Bound covariance of two discrete random variables Let $X,Y$ be two random variables over a discrete probability space, such that $X \in [0,1]$ and $Y \in [0,1]$.  I want to prove that $$ |\text{Cov}[X,Y]| \leq \sqrt{0.5 \; I[X,Y]}$$ where $I[]$ is the mutual information of the variables.  Is there an "elegant" way to prove that?  Some smart argument rather than technical analysis.

This follows from Pinsker's inequality. The inequality states that for any two distributions (here, discrete) $P$, and $Q$, it holds that

$$\|P-Q\| \le \sqrt{2D_{\text{KL}}(P\|Q)} $$
where $D_{\text{KL}}(\cdot \|\cdot)$ is the Kullback–Leibler divergence and $|P-Q|$ is their total variation.

For the right-hand side, recall that for any $X,Y$ random variables with joint distribution $p_{x,y}(x,y)$ and marginals $p_x(x)$, $p_y(y)$, we have
$$I(X,Y) = D_{\text{KL}}(p_{x,y} \| p_x p_y).$$

So if we define $P = p_{x,y}$ and $Q=p_xp_y$, we obtain the desired right-hand side.

On the other hand, by definition,
$$
\begin{align}
\| P - Q\| & = \sum_{x,y}|p(x,y) - p_x(x)p_y(y)| \\
& \ge \sum_{x,y}|p(x,y) - p_x(x)p_y(y)| \cdot xy \\
& = \sum_{x,y}|p(x,y)xy - p_x(x)x\cdot  p_y(y)y|\\
& \ge \left|\sum_{x,y} \left(p(x,y)xy - p_x(x)x\cdot  p_y(y)y\right)\right|\\
& = \left|E[XY] - E[X]E[Y]\right| \\
&= |\text{cov}(X,Y)|.
\end{align}
$$
The first equality follows since $x,y \in [0,1]$ and each term is non-negative. The rest of the derivation is mostly algebra. I'm probably missing a factor 2 of the normalization of the total variation. This will give the right constant inside the square root.


Is $\{ w \in L : wx \in L, \textrm{for some } x \neq \epsilon\}$ a CFG language if $L$ is CFG? Let $L$ be CFG. Is $\{ w \in L : wx \in L, \textrm{for some } x \neq \epsilon\}$ also CFG?

Consider the language
$$
L = \{ a^n b^m c^nd : n,m \geq 0 \} \cup \{ a^n b^m c^m d^2 : n,m \geq 0 \}.
$$
Then $\{ w \in L : wx \in L \text{ for some } x \neq \epsilon \} \cap a^* b^* c^* d = \{ a^n b^n c^n d : n \geq 0 \}$.

Here is a similar example, showing that if $L$ is context-free then $L \cap L \Sigma^+$ is not necessarily context-free:
$$
L = \{ a^n b^n : n \geq 0 \} \cup \{ a^n b^m c^m : n,m \geq 0 \}.
$$
Indeed, in this case $L \cap L\Sigma^+ = \{ a^n b^n c^n : n \geq 0 \}$.

The situation is likely different for deterministic context-free languages.


Is there a "flaw" in the backpropagation algorithm? While trying to find a better backpropagation algorithm, I came across a paradox in my algorithm and then I found out this also happens in the usual backpropagation algorithm.

Our neural network looks like this:

In this simple example, we have no biases. The activiation function is the usual
$f(x)=\frac{1}{1+e^{-x}}$

Our training set is just one datapoint: input = 0.9 and target_output = 0.9. The learning factor is set to 0.1.

The paradox happens when w2 is randomly initialized to a negative value. First, let's take a look at the "normal" situation (where the paradox does not happen). Let's say w1 and w2 are both positive, but the output is less than 0.9. w1 and w2 are both initialized at 0.1. Then to reduce the error, both w1 and w2 are increased, so the the output will get closer to 0.9. This is visible in the next graph (x is the training iteration, each training iteration contains one backpropagation).

Now let's take a look at the situation that w1 is intialized at 0.1 and w2 is initialized with a negative value (-0.5). Initially, an increase in w1 would cause a more negative value for the output layer, which increases the error. However, that's only the case because w2 is negative. Although w1 will decrease in the beginning, it will start increasing as soon as w2 becomes positive. The blue line (w1) is clearly decreasing in the beginning in the below graph from my experiment:

This "wrong" learning in the beginning of the blue line w1, is a consequence of using the derivative of the error function to induce small learning steps. Would it be better to somehow anticipate a positive w2 that will be needed anyway and so increase w1 from the beginning instead? Can we make a better backpropagation algorithm?

There's no paradox.  This is not a flaw.  Nothing is going wrong here.  In both examples, you're making steady progress: the output steadily gets (monotonically) closer and closer to the target.

Looking at individual weights (like w1 or w2), there's no reason to expect them to vary monotonically during the learning process.  If we perfect foresight and we know what the final optimal values of the weights are, we'd know whether each weight needs to increase or decrease -- but we don't.

Remember that backpropagation is just gradient descent, used to minimize some loss function.  Gradient descent is a local method for optimization: it makes a locally greedy step.  It has no global knowledge and as a result if you look at any single weight (any single coordinate), it won't necessarily vary monotonically: it might increase and then decrease, for instance.

Can you improve on backpropagation?  Yes, you can.  A large part of the success of deep learning is that researchers have found improvements to gradient descent for training neural networks (e.g., learning rate, momentum, and more).  Nonetheless, they're still optimization methods that work by taking a locally optimal step, and so they can be subject to overshoot and to phenomena such as you noticed.  Multidimensional optimization is hard.  You're going to see this kind of thing happen in pretty much any iterative method for optimization.

Bottom line: This isn't a flaw, this is only to be expected, given the difficulty of multidimensional optimization.  You still get to optimal values in the end, and that's almost-miraculous in its own right -- you should be glad for that and not worry too much about the fact that it takes longer to get there than if we already knew what the optimal solution was before we began.


What language should the following DFA recognise? My question is: what language should the following DFA recognise?

It seems that it should contain an odd number of substrings in the form 11*0. However, I am not sure whether there are any other conditions.

Arrive at the answer by following all paths from the start state to the accepting state identifying the 'tail recursion':

  0*1+0+(1+0+1+0+)*
= 0*1*100*(1*100*1*100*)*
= 0*11*00*(11*00*11*00*)*

Intuitively, these are all strings over {0,1}* with an odd number of 10 substrings which is equivalent to the characterization you gave.


Are there any known AM-complete problems/is AM-complete well defined? I'm curious about whether there are any complete problems in the Arthur-Merlin complexity class. Graph Non-Isomorphism (GNI) seems to be the canonical example of a problem in AM, but it's probably not a complete one.

I suppose I'm also wondering if a "complete" problem is well-defined for AM. Since AM = BP.NP, it seems the go to "reduction" to AM relies on randomized reductions to 3SAT rather than the Karp reductions we use for deterministic complexity classes. So maybe since Karp reductions have no error, "Karp reducing to an AM problem" doesn't really have any meaning, thus invalidating the usual notion we use of a "complete" problem?

Since AM = BP.NP, it seems the go to "reduction" to AM relies on randomized reductions to 3SAT rather than the Karp reductions we use for deterministic complexity classes.

This is a wrong intuition. Regardless of how you define your complexity class $\mathbb{C}$, if there exists any problem $\mathrm{A}\in \mathbb{C}$ such that for every problem $\mathrm{B}\in \mathbb{C}$, you have $\mathrm{B} \leq_p \mathrm{A}$, then $\mathrm{A}$ is a many-one complete problem of $\mathbb{C}$.

In fact, even a problem that is complete by randomized reductions for $\mathrm{AM}$ is not known. Put in other word, it seems very hard to just pin down any particular decision problem in $\mathrm{AM}$ so that we can have some non-trivial reduction from other problems known to be in $\mathrm{AM}$.

  See mathoverflow.net/questions/34469 and cstheory.stackexchange.com/questions/1233; in short, the definition of AM relies on a promise, and this makes it tricky to define a reduction. – sdcvvc

That is one of the obstacles on the way to find a complete problem for $\mathrm{AM}$. This is also applicable to $\mathrm{BPP}$, $\mathrm{RP}$, $\mathrm{co}$-$\mathrm{RP}$, $\mathrm{ZPP}$. These classes requires the poly-time probabilistic Turing machine to have bounded error probability on all instances. The situation is much easier for $\mathrm{PP}$, this class does not put any requirement on the error probability, whichever result has the higher probability is the answer of the machine so we can easily catch a complete problem for it, namely $\mathrm{MAJ}$-$\mathrm{SAT}$.


I'm looking for an algorithm to find unknown patterns in a string I am trying to detect patterns in huge code bases.
I managed to filter the entire codebase into a tagged string,
as in:
ABACBABAABBCBABA

The result should be:
ABA *3
CBA *2

I'm trying to build / use an algorithm which will find ANY unknown repeating pattern inside the string. The length of the pattern, it's composition, and the number of repeats is unknow.

To be a pattern it must occur atleast twice. And have atleast 2 items.
Once I detect the patterns I can represent them back in their original context

I have tried iterating over each tag.
For each tag find the following tag in the string.
continue until adding a tag matches only one repeat - hence no more pattern.

I get lost in implemetation (in JS or Python) and I'm hoping there is a better way.
Thanks.

Construct the suffix tree of your string, which takes time linear in the length of the string (assuming a finite alphabet). Every inner node represents a repeat, their respective descendant leaves encode the positions.


Partition of a set of integer into 3 subsets of approximately equal sum I'm having a very hard time trying to figure out how to solve this problem efficiently. Let me describe how it goes:

"A hard working mom bought several fruits with different nutritional values for her 3 kids, Amelia, Jessica and Bruno. Both girls are overweight, and they are very vicious and always leave poor Bruno with nothing, so their mother decided to share the food in the following manner:

Amelia being the heaviest one gets the most amount of Nutritional Value.
Jessica gets an amount equal or less than Amelia
Bruno gets an amount equal or less than Jessica, but you need to find a way to give him the highest possible nutritional value while respecting the rule ( $A \geq J \geq B$ )"

One of the test cases given by my teacher is the following:

The fruit list has the following values { 4, 2, 1, 8, 11, 5, 1

Input:
7   -----> Number of Fruits
4 2 1 8 11 5 1 ----> Fruits Nutritional Values

Output:
1 11  ---->  One fruit, their nutritional values sum for Amelia
5     ---->  Position of the fruit in the list
3 11  ---->  Three fruits, their nutritional values sum for Jessica
1 2 6 ---->  Position of the fruits in the list
3 10  ---->  Three fruits, their nutritional values sum for Bruno
3 4 7 ---->  Position of the fruits in the list

Note: I am aware that there are several ways of diving the fruits among the kids, but it doesn't really matter as long as it follows the rule $A \geq J \geq B$.

I'm trying to make a program in C# that solves this kind of problems but I need an efficient formula to make this work. Generating all the subsets is out of the question because it is very consuming task. The list of fruits can have up to $50$ elements, $2^{50}$ is a huge number.

Let $x_i,\ i=1\ldots,n$, be the list of nutritional values of the $n$ fruits, which I assume are nonnegative integers.

You want to partition $\{1,\ldots,n\}$ into three sets $A,B,C$ to maximize the minimum of $x_A = \sum_{i\in A} x_i$, $x_B = \sum_{i \in B} x_i$, $x_C = \sum_{i \in C} x_i$.  This is a variant of the set-partitioning problem.  It is NP-complete.

However, there is a dynamic programming algorithm that is pseudo-polynomial (i.e. polynomial in $n$ and $S = \sum_{i=1}^n x_i$). Namely, for $1 \le m \le n$, $u, v \ge 0$ with $u+v \le \sum_{i=1}^m x_i$, let
$T(m,u,v) = 1$ if there are disjoint subsets $A(m,u,v), B(m,u,v)$ of $\{1,\ldots,m\}$
such that $\sum_{i \in A(m,u,v)} x_i = u$ and $\sum_{i \in B(m,u,v)} x_i = v$, $T(m,u,v) = 0$ otherwise.
Thus
$$T(1,0,0) = T(1,0,x_1) = 1,\ T(1,u,v) = 0 \text{ otherwise.}$$
For $m > 1$,
$$T(m,u,v) = 1 \Longleftrightarrow T(m-1,u,v) + T(m-1,u-x_m,v) + T(m-1,u,v-x_m) \ge 1.$$

After computing all $T(m,u,v)$ using this recursion, you want to find the $(u,v)$ with $u$ as large as possible subject to $T(m,u,v) = 1$ and $u \le v \le S - u - v$.


Delivery Algorithm - Find shortest paths Given -

A center(lat=x,lng=y) 'C' from which a delivery boy makes a round
trip.
A delivery boy has a bag which may contain at the most 10
boxes to deliver.
A set of points Di (lat=xi,lng=yi) around 'C'
where the delivery has to be done. D=number of Di & 1<=D<=10
Each Di either belongs to time window(30 minutes) W1 or W2 where W1 is
something like 11-30 am to 12 pm and W2 like 12 pm to 12-30 pm
Each delivery has to meet an SLA (service level agreement). Eg-  If the order O1 at drop point D1 belongs to W1 then it must be delivered within W1 window.

Task - Find the shortest time path such that the delivery boy meets SLA for maximum number of orders. The best path is the one where SLA is met for all orders..

I think it will be better if I start with a couple of variations.. Use these variations in dry runs and gather some data for each of the variations..

What I am looking for - Any other cues/variations that I can use.. The greedy approach is already up and running. I am gathering real time data to measure its performance..

CLARIFICATIONS

If SLA's can't be met, do the deliveries still need to be made? - Yes, in those cases the best algorithm will be the one with  minimum SLA breaches..followed by minimum time..

Are there algorithm constraints/metrics (I.E. execution speed, memory used,etc) that must be considered? - Speed - not so much an issue - even if it takes 1 minute to run algo its ok, memory - it may take upto 0.5 gb.. Also if it turns out to be very compute intensive.. I can buy a new machine for running this algo..

Will you need to scale up beyond the relatively small inputs stated - NO. The delivery boys capacity is fixed. It may at the most become 15 (from 10 earlier)

A max of 10-15 orders is small enough that you might be able to brute force it.  While this would exceed your execution time limit, it might be worth doing so on a small number of problems in order to compare algorithms absolutely rather than relatively.  Alternatively, you might be able to find precomputed benchmarks for this problem.

In general, I'm personally found of restricting routing problems to a Deluaney triangulation.  It's fast to calculate and has a Euclidean minimum spanning tree  (MSP) as a subset.  It won't have any route crossings (like those removed by a 2-opt).

However, the SLA constraint may work against that.  E.G. Say that the you have found an optimal TSP solution (a locally optimal solution) for W1, but it can only service k out of n orders in time.  In that case the globally optimal solution may require delaying the last (n-k) orders in W1 and going to the clostest order in W2.  There's no reason to expect this W1 to W2 switch-over arch to be in a DT over all the sites.  Furthermore, if your time windows don't overlap, there's no reason to visit W2 site during the W1 phase.

So then, I'd find a MSP for each subset of order sites (W1 & W2).  On W1, apply Christofide's algorithm to get a Hamiltonian cycle.  Find the start node, call it S1, & remove its longest arc in the cycle to get a Hamiltonian path through all of W1 - call this P1.

Next, compute the travel time & check for broken SLAs on P1.  Eject the site that yeilds the biggest time savings until all remaining SLAs on P1 are valid.

Find the clostest point in W2 to the last site in P1 - call this S2.

On W2, apply Christofide's.  Find S2 & remove its longest arc in the cycle to get a path through all of W2.

Recompute the travel time for P1 + P2 & check for broken SLAs on P2.  Eject the site that yeilds the biggest time savings until all remaining SLAs on P2 are valid.

Finally, let W3 be all the previously ejected sites. Find the clostest point in W3 to the last site in P2 - call this S3.  Find a MSP on W3, apply christofides, find the S3 & remove its longest arc in the cycle to get a path.

Solution is concatenation of P1, P2, P3, S1.  Clearly, there are cases where this won't give the optimal answer, but it should scale well & has known bounds on the sub-problems which might help in determining its overall bounds.


Represent polynomial time complexity as linearythmic To determine the experimental time complexity of radix sort, I wrote a program that counted the number of steps the algorithm took to sort N points. I ran that program for multiple N length arrays, and I plotted the steps taken in Excel. Then, using the trend line tool, I calculated the polynomial that best fit the function.

It gave me something along the line :
$$Steps = 16n^{1.0932}$$

This seems to be $O(n)$, but my prof is telling us to represent this as $O(n \log n)$ . How would I go about to demonstrate this.

Thanks.

PS: If anyone is interested, here are my results.

You cannot "demonstrate" that a running time is $\Theta(n\log n)$ experimentally. All you can do is give evidence. Such evidence would be a constant $C$ such that for large $n$, $Cn\log n$ is a good approximation to the empirical running time.

You found the best polynomial approximation to your input. Since $Cn\log n$ is not a polynomial, this kind of approach cannot possibly give you the answer $Cn\log n$. If you want $Cn\log n$ to be a possible answer, you need to include such functions in the family of functions you are optimizing over.

Finally, to demonstrate that $Cn\log n$ is a better approximation that your polynomial approximation or a linear approximation, all you have to do is to compare the error in the approximation $Cn\log n$ to the errors in the other two options. Smallest error wins.


Solving T(n) = 3T(n/3)+n/2 using master method I thought I understood the Master Method quite well till I saw this question

$T(n) = 3T(\frac{n}{3})+\frac{n}{2}$

My approach:
  $a = 3 ; b=3$ and $f(n) = \frac{n}{2}$

$n^{\log_b{a}}$ = $n^{log_3{3}} = n$

This looked like a classic solution of master method using case 1.

But since case 1 implies $f(n) = n^{\log_3{3} - ε}$ and I cannot find any way that ε can be represented, I understand that case 1 is not the way.

However the solution says that this is solvable by case 2 of the master method and the solution is  $T(n) = \theta(n^{log_3{3}} \log^{ n}) $

Case 2 of the master method states that if $f(n) = n^{log_b{a}}  \log^{k}{ n}$ then $T(n) = \theta(n^{log_b{a}} \log^{k+1}{ n}) $

Can someone explain how this is solved using case 2 of the master method and why this fits under case 2?

While applying master's theorem all you have to do is compare which of $f(n)$ or $(n^{\log_b{a}})$ is asymptotically greater. The greater of the two functions determines the solution to the recurrence. There are only possible outcomes for this comparison:
[1] $(n^{\log_b{a}})$ is asymptotically greater than $f(n)$
[2] Both are asymptotically equal
[3] $f(n)$ is asymptotically greater than $(n^{\log_b{a}})$

Yours falls in case 2.


Count combinations differing by fixed number of elements I'll try to formulate my problem through an example.
Lets suppose we have a collection of items of type a,b,c,d,e,f.

a1, a5, a7
b2, b3
c5, c6, c7, c8
d4, d5
e1, e2, e3
f3, f7, f8

If we take one element from each type there are 3*2*4*2*3*3 abcdef lines (combinations).

We have another random line
a1b5c7d1e5f7.

I want to count how many from the combinations lines differ by the current line in exactly 3 elements.
I.e these lines differ only in one (the first) element

a5b5c7d1e5f7
a8b5c7d1e5f7

I want to do that if it's possible without generating and comparing each combination.

The trick to this count is to fix the elements that will be different, then calculate how many different choices we have for this set of elements. For each selected element we will have one less choice then we did originally, and for the elements which are to be the same we have one choice for that character. Let $V$ be the vector of the character set counts for the positions. In your example we would have $V=[3,2,4,2,3,3]$ and let $t$ be the number of differences. For each t-tuple $x$ (set of t positions) we have  $\prod_{i \in x} (V[i]-1)$ strings which differ in exactly those places. The final answer is the sum of this for every t-subset of the positions. Since you character set differs for each position you will need to go through all of the t-tuples to solve this. That is not overly bad since though since the number of t-tuples is polynomial instead of exponential as checking all combinations could have been.


Difference between Dominant strategy and Winning Strategy I am a little bit confused by the definition of dominant strategy and winning strategy, what's the difference between them.

Following are the definitions taken from wikipedia, below every definition I added some thoughts. If you fell that my thoughts are not correct or ambigues please let me know.

  Dominant strategy.In game theory, dominant strategy (commonly called simply dominance) occurs when one strategy is better than another strategy for one player, no matter how that player's opponents may play. Many simple games can be solved using dominance.

The first interesting note is that the term dominant strategy is applied only to two different strategies, and more precisely it's should be defined as "A is dominant strategy over B", actually the notion "dominant strategy" might be relevant to the game itself in this case the dominant strategy A dominates over all other strategies of the player.

  Winning strategy.A strategy is winning if the player following it must necessarily win, no matter what his opponent plays.

This notion sounds like stronger notion than dominant strategy, because having winning strategy its guaranteed that the player wins if he follows the strategy no matter what the opponent does, on the other hand dominant strategy does not guaranteed the win, it only says that dominant strategy guarantees the best possible outcome for the player over all possible player's strategies and no matter what the opponent does.

I would to emphasize one common property for the dominant strategy and the winning strategy they both determined by the outcome of the game and don't depend on the strategy of the opponent.

In my opinion, winning strategy is always a dominant strategy, but vice verse is not always true.

Do you agree with the intuitive understand and thought?

Your intuition seems mostly correct. However don't forget that not all games are winner vs. loser, see e.g. Coordination games. The meaning of a winning strategy is somewhat meaningless there, unless you define the winner to be the one with the greater outcome (or allow multiple winners which gain more than a certain threshold). Dominance is still an important tool for those strategies.

There is another problem, because your definition of domination includes "better" in any case. This is a strict dominance. A weak dominance means "at least as good as" in all cases and "better" in at least one case, where case means an opponents strategy (or a set of strategies for multiple opponents).

Possible outcomes are only $\{\text{win},\text{lose}\}$: A winning strategy for you results in $\text{win}$ for any strategy of the opponent and is thus weakly dominant compared to any non-winning strategy, if there is one. But in many games an opponent can play so badly, that some non-winning strategies lead to a win nevertheless and so they are not strictly dominated by a winning strategy. But more important than the dominance of winning strategies is the dominance between non-winning strategies of your opponent. If s/he has a weakly dominant strategy relative to all other strategies and you can win against this single strategy, you have a winning strategy.
Possible outcomes are some set linear ordered set $A$ and you win, if your profit is greater than that of the opponent (this is not a usual definition, one would use other tools like equilibria in this case). For example in the following table each player has two strategies and yours correspond to the rows (each cell is: your outcome, others outcome):
$$\matrix{10,12&\mid &10,12\\\hline\\7,4 &\mid&7,4}$$
If you choose the second strategy you'll always win and if you choose the first one, you'll lose, but your outcome is higher, so choosing row $1$ dominates a winning strategy.

Resumé: Dominance is a much broader concept and for many  but not all games winning strategies are weakly dominant to at least one other strategy.


If the speed of electrical charge hasn't changed, how have computers become faster? Everyone knows computing speed has drastically increased since their invention, and it looks set to continue. But one thing is puzzling me: if you ran an electrical current through a material today, it would travel at the same speed as if you did it with the same material 50 years ago.

With that in mind, how is it computers have become faster? What main area of processor design is it that has given these incredible speed increases?

I thought maybe it could be one or more of the following:

Smaller processors (less distance for the current to travel, but it just seems to me like you'd only be able to make marginal gains here).
Better materials

if you ran an electrical current through a material today, it would travel at the same speed as if you did it with the same material 50 years ago.

  With that in mind, how is it computers have become faster? What main area of processor design is it that has given these incredible speed increases?

You get erroneous conclusions because your initial hypothesis is wrong: you think that CPU speed is equivalent to the speed of the electrons in the CPU.

In fact, the CPU is some synchronous digital logic. The limit for its speed is that the output of a logical equation shall be stable within one clock period. With the logic implemented with transistors, the limit is mainly linked to the time required to make transistors switch. By reducing their channel size, we are able to make them switch faster. This is the main reason for improvement in max frequency of CPUs for 50 years. Today, we also modify the shape of the transistors to increase their switching speed, but, as far as I know, only Intel, Global Foundries and TSMC are able to create FinFETs today.

Yet, there are some other ways to improve the maximum clock speed of a CPU: if you split your logical equation into several smaller ones, you can make each step faster, and have a higher clock speed. You also need more clock periods to perform the same action, but, using pipelining techniques, you can make the rate of instructions per second follow your clock rate.

Today, the speed of electrons has become a limit: at 10GHz, an electric signal can't be propagated on more than 3cm. This is roughly the size of current processors. To avoid this issue, you may have several independent synchronous domains in your chip, reducing the constraints on signal propagation. But this is only one limiting factor, amongst transistor switching speed, heat dissipation, EMC, and probably others (but I'm not in the silicon foundry industry).


Transitive reduction of DAG I am looking for O(V+E) algorithm for finding the transitive reduction given a DAG.

That is remove as many edges as possible so that if you could reach v from u, for arbitrary v and u, you can still reach after removal of edges.

If this is a standard problem, please point me to some model solution.

We can solve this problem just by doing DFS from each vertex.

For each vertex $u \in G$, start the DFS from each vertex $v$ such that $v$ is the direct descendant of $u$, ie. $(u,v)$ is an edge.
For each vertex $v'$ reachable by the DFS from $v$, remove the edge $(u, v')$.

The overall complexity of the above is the complexity of running $N$ DFS', which is $O(N(N+M))$.


Calculate Shortest Path (Shortest Time) Through a Store in a Graph There is an undirected graph and some of the vertices are said to be stores.
Person A wants to reach to person B with a present. That means person A has to stop by one of the vertices marked as stores and get the present first before ever reaching to person B. Moreover, each store has a specific waiting time, and if the person decides to stop by at that particular supermarket, the waiting time should be included in the shortest path(shortest time).

Well, regular Dijkstra does not work very well because the shortest path may not include any store vertices, so the stores should somehow be incorporated in the algorithm. It is a must to visit one of the vertices marked as a store. But total travel time has to be the minimum.

Only the vertices marked as stores have weights, and it is a must to visit at least one of them.

You can do this with two instances of shortest paths.

You need to know the shortest distance $d(A,S)$ for each store $S$. This is just Dijkstra from source $A$.
You also need to know all the shortest paths from each store to B; i.e. $d(S,B)$ for each store $S$. This can be done by reversing the edges in the graph and running Dijkstra from source $B$.

Once you have these two, all you need to do is compute the min over paths that stop at a store, including the weight $w$ of the store.

$\min_S \left(d(A,S) + w(S) + d(S,B)\right)$

Asymptotically, in total, this is no more expensive than just running Dijkstra's algorithm. In practice you can stop early in each instance of Dijkstra once you've seen all of the stores.


Estimate distribution of a composite variable Suppose I have N sets of numbers (10 numbers per set) {a1, ....., a10}. I form a sum by taking one number at random from each set. SUM = num from set 1 +......+ num from set N. If I do this a large number of times I will generate a large number of different values for the SUM variable. How can I estimate the distribution of the SUM values (P10, P50, P90 etc.)?

Use a convolution.

For instance, write the generating function for each set, then multiply the generating functions; this gives you the generating function for the distribution of the sum.

This gives you the exact distribution (which is even better than an approximation!).


Examples for lower bounds proof except sorting After i read this question here.

All non-trivial examples of lower bounds always mention sorting, but i do not find other non-trivial examples, which do not rely (partly) on the sorting proof.

What are other non-trivial examples?

Here are some examples:

Finding an element in a sorted list takes time $\Omega(\log n)$ in the RAM model.
Implementing a disjoint sets data structure requires an amortized $\Omega(\alpha(n))$ operations in the cell probe model.
Determining whether the input string is a palindrome requires $\Omega(n^2)$ operations on a single tape Turing machine.

There are many others.


Solving the graph colourability problem in polynomial time if the equivallent decision problem is in $P$ For the graph colourability problem, we are given a graph and our goal is to find a colouring of the graph with the fewest possible number of colours so that no two adjacent vertices have the same colour. This problem is known to be NP complete.

Suppose that we have an algorithm $A$ that runs in polynomial time and tells us whether our graph can be coloured by using $\leq k$ colours. We can query this algorithm as many times as we want.

Would this imply that the graph colourability problem also be in $P$?

My approach would be to begin querying for $k=1$, and then keep incrementing $k$ until we get a positive response from $A$, which is going to be the answer to our problem.

However, if we know how many colours we can use to colour our graph, how do we then actually colour each node? Is there a known algorithm for this?

Hint: If there is a valid coloring in which vertices $x,y$ get the same color then the graph resulting from merging $x,y$ into a single vertex has the same chromatic number. Otherwise, you can add an edge between them (if it doesn't already exist). Either way, the graph "simplifies" (either the number of vertices decreases, or the graph gets closer to a clique).


Showing Regular Languages are closed under removal of rightmost character "Show that if L is a regular language without the empty string, then the language in which the rightmost symbol of every string in is removed is also regular."

I tried going by closure properties of regular languages but got nowhere.. I said L' = {x| y is in L and xa = y, for some a in the alphabet} and didn't really know where to go from there... I also tried to argue that since L is a regular language, it can be expressed by some regex..and I wanted to show by cases that we can form a new regex by omitting the last unit of regex? But that seemed flawed. I also tried creating a skeleton dfa for L and just changing the set of accepting states to the states that transition into the previous final states.. I feel like there is a gap in my knowledge and would really appreciate it if someone could not only help me figure out the solution but also give me some advice on how to approach such problems and fill the gaps in my knowledge!

This is just a special case of right quotient. Specifically, for a language $L$ over an alphabet $\Sigma$, this is $L / \Sigma$.

Many textbooks and course notes contain proof of regular languages' closure under right quotient. For example, here, on page 10.


How P2P search engines prevent corruption of distributed index by malicious peers? As a hobby, I am writing a simple and primitive distributed web search engine. It occurred to me that it currently has no protection against malicious peers trying to skew the search results.

The principle idea of the project is:

To store the inverse indices and ranking factors in a Kad (Kademlia) DHT (Distributed Hash Table).
The peers update the inverse indices as they crawl web.

I used Google Scholar to find a solution. It seems that most of the authors of proposed P2P web search ignores the above-mentioned problem.

I think I need some kind of reputation system or trust metrics. My knowledge in this domain is sufficiently lacking. I would very much appreciate a few pointers.

When tackling such problems, think in general terms. Researchers have studied the impact of malicious peers in numerous papers. Most of these systems should work.

However, define your problem clearly. Ex: What are the malicious peers trying to do in this case? do you want to:

protect your system from unwanted outsiders (security),
protect your data from faulty peers (fault tolerance),
protect your data from greedy peers (greedy peers),
or others?

Also note that Kademlia is very similar to Chord, SkipNet, Pastry and others (some researchers call these networks "common prefix networks - I can't remember", others: ring-based p2p networks, etc ... Some solutions may be designed specifically for these networks.  However, I don't see why a solution made for a structured P2P networks would not work for your architecture.


Proving at least $n-1$ comparisons are needed to test if an array is sorted so I need to prove the following:

Prove that $n-1$ comparisons are sometimes necessary to test whether an array with $n$ distinct elements is sorted in increasing order, for any $n \geq 1$.

The problem comes with the following hint:

Assume an algorithm exists that always correctly tests if the array is sorted using at most $n-2$ comparisons and show there must exist an input where this algorithm fails.

Base on the hint, I tried proving this via contradiction and here is my attempt:

Assume an algorithm exists that correctly tests if the array is sorted using at most $n-2$ comparisons. Then, let A be an array of 2 random numbers $a$ and $b$. Given that we don't know the value of $a$ with relation to $b$ or vice versa, in order to find this relation, an thus find out if the array with n-distinct elements is sorted in increasing order, 1 comparison operation, namely between $a$ and $b$, is needed, but then $n-2 = 1-2 \neq 1$. Therefore we have arrived at a contradiction.

While this attempt is most likely wrong, I am somewhat familiar with proofs by contradiction, but I don't see how deriving a contradiction from my initial assumption (the one from the hint) helps prove that $n-1$ comparisons are necessary.

You can use a simple adversary argument (in Jeff's lecture note) to prove that every correct algorithm has to compare $a_i$ with $a_{i+1}$ for $i=0,1, \ldots, n−2$.

If it is not the case, you can carefully choose the values such that $a_{i+1} < a_{i}$, without violating any other comparison results.

You are encouraged to fill the details.


MAXSAT approximation We have been studying a 1/2-approximation for MAXSAT which runs in expected polynomial time, by randomly assigning True/False to each variable and repeating until we reach an assignment with at least half of clauses satisfied.

I don't understand why the algorithm needs to be so complicated. Why does the following not give a 1/2-approximation for MAXSAT in guaranteed linear time?

Let $m$ be the number of clauses in the formula.
Set all variables to true. Count the number of satisfied clauses. If it's at least $m/2$ then return this assignment.
Set all variables to false. Return this assignment.

Every clause contains at least one literal which will be satisfied either by setting a variable to true or a variable to false. Thus the two assignments satisfy a total of at least $m$ clauses so at least one of them satisfies $\ge m/2$ clauses.

I won't speculate about your teacher's reasons for including the random assignment algorithm over yours. However, one advantage of random assignment is that, if every clause has at least $k$ literals, it's actually a $(1-2^{-k})$-approximation (Wikipedia cites this to Vazirani's book). Your suggestion is still only a $\tfrac12$-approximation in this case (consider a formula where half the variables appear only in clauses where every literal is positive and the rest appear only in clauses where every literal is negative, and half the clauses are all-positive, half all-negative).


Why do we need value-returning functions? I'm just a beginner at C++ programming. I am currently having hard time grasping the usage of value returning function and non-value returning function. Void functions are called non-value returning function but they can return value if we assign certain parameters, compute the parameters and call them in the main function. So, doesn't this defeat the purpose? I feel like I am getting this wrong, so some explanation here would be great!

Also, I see that void functions are easier to use, since I don't need to use " cout<< 'the void function' << endl; "
It seems easier and the value-returning function seems useless. I need explanation here as well as to why we need value-returning function.

Please bear with my questions and I am always ready to learn!

"Need" as such, no. There you are right, all the work can be done using void functions, by passing pointers to variables to modify instead, or changing global variables. In fact, everything is compiled down to assembly language, and no such language I know of has "functions" that return values.

On the other hand, we are accustomed (by mathematics, and by lots of it's applications in everyday life) to think in terms of functions that are applied to arguments and return a value. Think of sin x, square root, and a long list of others, like lowly strlen() in C. It is a nice simplification to be able to say:

y = abs(x) - 42 * sqrt(b);

instead of something like:

pabs(x, &xa);
psrqrt(b, &ba);
y = xa - 42 * ba;

Come to think about it, multiplication and subtractions are functions returning values too (X& operator*(const X&, const X&) and X& operator-(const X&, const X&) in C++), and the handling of results and intermediate values soon gets unmanageable. One of the points of a programming language is to handle such bureaucratic details for you, transparently.


How do I search for Verification of Quantum Computing So, in quantum computing, each qbit has a 50/50 chance of being in either the state of 1 or 0 when you measure it. Simple enough.

But I've heard reports a while ago about some company having successfully added two relatively small numbers and gotten out the right answer the majority of the time. The question I am trying to solve is: How? How would you verify a quantum result (without assuming you have the answer already available that you can compare it to)?

That, however, is not what I'm asking of this Stack Exchange. Instead, I am wanting to know what search terms in Google I can use to find this answer. "how to verify quantum computing results" doesn't turn up anything more than 1 academic paper (which I am actually reasonably confident has the answer I'm looking for). At least with the search, I get nothing more that is relevant to what I'm actually looking for.

Thus why I come here in hopes that someone might actually know what I would need to search to get more relevant results.

The answer is, when working with sufficiently small numbers, we can simulate the quantum process on a classical computer.  It might take exponentially longer on the classical computer, but for small numbers, that's still feasible (the exponential of a small number is still not too large).

See Question 6 at Scott Aaronson's FAQ (https://www.scottaaronson.com/blog/?p=4317) as well as part (2) of https://www.scottaaronson.com/blog/?p=4372.


Virtual Address and Physical Address Space A machine has 48-bit virtual addresses and 32-bit physical addresses. Pages are 8K. How many entries are needed for a conventional page table ?

The answer is 2^35 entries

Why not (2^32) / (2^13) = 2^19 entries...?

My doubt here is why does the number of page table entries depend on virtual address space rather than physical address space?

What does it mean to have more virtual address space than physical address space? The process can only access as many pages present in the physical memory. So it makes sense to have same have both virtual and physical memory address space same. But why have more virtual address space?
Does it mean 2 different virtual address entries are mapped to the same physical location in the same page table? Guess that would lead to inconsistency right? Can someone help me get the bigger picture here..... I really need to internalize this concept.

When we are using Virtual Memory, we are translating from a Virtual Address Space to a Physical Address Space.

To understand why it requires $2^{35}$ entries, consider the page size. In order to byte address $8$KB, we require $2^{13}$ entries. If we consider the Virtual Address given to us of $48$ bits, this gives us $48-13=35$ bits. These are the bits that are used for indexing into the page table for determining the address of the page or 'frame' in main memory.

The reason for having more virtual memory is because programs were getting so large that they couldn't be fit in main memory. So in order to allow a greater degree of multiprogramming, virtual memory was introduced. A program could have a 'large' memory to itself. However only the required parts would be loaded into memory as and when required a concept refered to as Demand Paging.


Is WPA2 with pre-shared key an example of a zero-knowledge proof? When setting up an access point and selecting WPA2, one must manually enter a pre-shared key (a password), PSK, into both the AP and the STA.

Both parties, AP and STA, must authenticate each other. But they have to do so without revealing the PSK. Both have to proof to the other party that they know the PSK without actually sending it.

Is that an example of a zero-knowledge proof?

I thought it was, but nothing legit shows up when I google for zero-knowledge proof and WPA2 or EPA-PSK (the authentication method used).

In authentication you often come accross zero-knowledge password proof (ZKPP). EAP itself is a rather generic framework and it might involve revealing the identity of the client for instance to transfer it to the next layer of authentication such as RADIUS.

PACE (BSI TR-03110) is one example of ZKPP protocols used for authentication. EAP-SPEKE is another.

The security of the key relies on the use of only parts of the key in the exchange between the client and the server. The client offers a nonce encrypted with the key to the server. Therefore a rogue server receives a encrypted nonce and holds its plaintext version. This is not zero-knowledge, since in a finite time a rogue server might accumulate enough information to break the AES-128 encryption.

Hence EAP-PSK may not be considered an example of zero-knowledge password proof, though other proposed authentication schemes based on EAP such as EAP-SPEKE have this property.

To illustrate the problematic part of the EAP-PSK protocol consider the message flow as presented in RFC 4764.

  The first message is sent by the server to the peer to:

  *  Send a 16-byte random challenge (RAND_S).  RAND_S was called RA
     in Section 3.2

  *  State its identity (ID_S).  ID_S was denoted by A in
     Section 3.2.

  o  The second message is sent by the peer to the server to:

  *  Send another 16-byte random challenge (RAND_P).  RAND_P was
     called RB in Section 3.2

  *  State its identity (ID_P).  ID_P was denoted by B in
     Section 3.2.

  *  Authenticate to the server by proving that it is able to
     compute a particular MAC (MAC_P), which is a function of the
     two challenges and AK:
     MAC_P = CMAC-AES-128(AK, ID_P||ID_S||RAND_S||RAND_P)

  o  The third message is sent by the server to the peer to:

  *  Authenticate to the peer by proving that it is able to compute
     another MAC (MAC_S), which is a function of the peer's
     challenge and AK:
     MAC_S = CMAC-AES-128(AK, ID_S||RAND_P)

Here AK is a part of the secret key that is used at this stage and may be revealed to the rogue server that is able to decrypt AES-128.


Longest common substring many strings to one I'd like to find longest common substring (occurrences, start index) between one string and many others.

For example

source string - "abcdefghijklmncdop"
other strings - ["cd", "ghi",
"mn", "zw", "cdewxyz"].
Expected result -(original string, substring, index in source string) =  [(cd,cd,2),(cd,cd,14),(ghi,ghi,7 ),...(cdewxyz, cde, 3]

I could create suffix array from the source string and search all possible substring occurrences sequentially - but it doesn't seem that efficient. The other strings array might be very large, so creating joint arrays with special delimiter is not considered.

I also thought on creating suffix tree, but I there are many source strings soe space complexity might become an issue.

Let's assume you have already built suffix tree for string $S$. Then for any string $T$ you can find $\mathtt{LCS}(S, T)$ in $\mathcal{O}(|T|)$ time, $\mathcal{O}(1)$ space, and read-only access to the suffix tree.

Here's pseudocode that finds $M$ - location in the suffix tree (edge plus position on that edge) that corresponds to $\mathtt{LCS}(S, T)$:

M := C := ST.root

for i := 1..|T| do
  while C.canNotExtendWith(T[i]) do
    C := C.contract()

  C := C.extendWith(T[i])

  if C.length > M.length then
    M := C

Here:

ST.root is the suffix tree root
C.canNotExtendWith(x) returns true if you can't follow given letter $x$ from location $C$
If $C$ is a location of string $U$ in the tree, then C.extendWith(x) returns location of string $Ux$
If $C$ is a location of string $xU$, then C.contract() returns location of $U$ (i.e. follows the suffix link)
If $C$ is a location of string $U$, then C.length is $|U|$

Both correctness and $\mathcal{O}(|T|)$ time complexity follow from the Ukkonen's algorithm.

Hand-wavy explanation of the algorithm correctness:

If you can't extend the substring with single letter, there's no point in trying to extend it further
If you've already found a good candidate substring, there's no point in contracting it


Proving that context-free languages are closed under inserting symbols This is a theoretical computer science question, regarding the proof of whether or not context-free languages are closed under an operation.  This means basically that any context-free language which undergoes this operation would still be context-free.

  For a language $A$ which is a subset $\Sigma^*$, define the language $A_+$ as

  $\qquad\displaystyle A_+ = \{xyz | y\in \Sigma \wedge xz \in A\}$.

  Prove that the set of context-free languages is closed under the $+$ operator.

So $A_+$ contains all strings that can be obtained by inserting one symbol into a string in $A$.
Show that the class of context-free languages is closed under the operation $+$ (i.e.,     show that
if $A$ is context free, then $A_+$ is also context free).

Note that this is not a homework question.  Examples of closure proofs are sparse online and in my textbook.

First, let's think about the different ways to prove closure of CFLs:

Constructing a "template" Push Down Automata that can incorporate any other Push Down Automata and add on a part to the beginning, middle, or end of the PDA and still be able to accept the language accepted by the original CFL, with the new operation on it.  Basically, if for any given PDA P, if a PDA P' can be created which accepts the language of P with the new operation (in our case, the "+" operator) performed on it, then that operation must be under closure.

Solving the problem in this manner is quite simple to think about.  Imagine a PDA P which accepts strings from the CFL L.  In application to our problem, this would be a PDA which can successfully read in the string 'xz', where x and z are simply any string conforming to our alphabet.  The PDA P' would similarly have the ability to read xz, but each state of the PDA could have an additional self loop which reads the character in the string y.

I have selected the answer which I find to be most appropriate for this question.  It simply involves using the "tempate PDA" strategy which I outline above; however, my construction did not achieve the goals of the new language (think about why before looking at the answer below).

Using closure under GSM mappings

Whenever possible, it may be faster to prove closure properties from
other known closure properties, That is why there has been a
systematic study of closure properties (see AFL, full AFL, trios,
...). This is somewhat developed in the Hopcroft-Ullman textbook,
ed. 1978).

For this problem, the insertion of a single character from the alphabet in the strings of a
language can be trivially performed by application of a
GSM-mapping. Since CF languages (and many others) are closed under
GSM-mapping, they are closed under the $+$ operator.

If you do not know about GSM mappings, you can do it with closure
under intersection with regular sets, homomorphism and inverse
homomorphism. That is actually how closure under GSM mapping is
proved.

Assuming your original alphabet is called $\Sigma$, you create a new
alphabet $\hat\Sigma=\{\hat a \mid a\in \Sigma\}$, i.e. a new set of
symbols in 1-1 correspondance with $\Sigma$.  Using the inverse of a
homomorphism (that simply erases $\hat\Sigma$), you insert an arbitrary
number of $\hat\Sigma$ symbols in the string.  Then you intersect the
result with the regular set $\{w\in (\Sigma\cup\hat\Sigma)^*\mid
|w|_{\hat\Sigma}=1\}$, so as to allow the insertion of only one
symbol from $\hat\Sigma$. Then you remove the hat with a homomorphism $\phi$ such
that $\forall \hat a \in \hat\Sigma,\, \phi(\hat a)= a$.


Traveling Salesman Problem with Neural Network I was curious if there were any new developments in solving the traveling salesman problem using something like a Hopfield recurrent neural network.  I feel like I saw something about recent research getting a breakthrough in this, but I can't find the academic papers anywhere.  Is anyone aware of any new, novel developments in this area?

there are many papers on using artificial neural networks to solve TSP including recurrent and Hopfield networks, and they "succeed" in a rough sense, but so far there does not seem to be any evidence that the techniques are in any way (strongly?) superior to other algorithmic approaches, so its something more like a research curiosity at the moment. the use of ANNs for this problem is indeed counterintuitive from the pov of combinatorial algorithmics and the mechanisms by which the problem inputs/ outputs are encoded are novel and tend to vary, and maybe are not yet so standardized. the authors seem maybe more interested in demonstrating "proof of concept" and a comparison with other algorithm types seems more rare (there is some in the last paper). see eg

Traveling salesman problem using neural network techniques / Abdel-Moetty
Using Hopfield Networks to Solve Traveling Salesman Problems Based on Stable State
Analysis Technique / Feng, Douligeris
Comparison of Neural Networks for Solving the Travelling Salesman Problem / La Maire, Mladenov
A Recurrent Neural Network to Traveling
Salesman Problem / Siqueira, Scheer, Steiner


Approximation factor shorthand clarification I'm starting to dabble in the world of approximation algorithms and had a question about the convention many papers will use when talking about the approximation factor. I know that an approximation factor will give the factor within which the algorithm will perform with respect to the optimal solution. This is pretty easy to grasp for things like a 2-factor approximation. I've also seen other literature and lecture notes refer to $1-1/\epsilon$ when giving the probability and/or percentage of the optimal that will be returned (or, put another way, how "much" of the optimal an approximation algorithm will, well, approximate).

But I've seen some papers (like Linear-Time Approximation for Maximum Weight Matching
) refer to a $1-\epsilon$ approximation ratio. For example:

  we give an algorithm that computes a (1 − ε)-approximate maximum weight matching

So my question is: are they referring to the $1-1/\epsilon$ ratio that I've been seeing elsewhere? Apologies if this is a simplistic question, I'm just getting starting in learning about these very-cool algorithms and am trying to get my head around which papers are presenting things that are extraordinary vs. not as competitive compared to the optimal solution. Thank you!

That article, Linear-Time Approximation for Maximum Weight Matching calls "a matching $\delta$-approximate, where $\delta \in [0, 1]$, if its weight is at least a factor $\delta$ of the optimum matching."

That $\delta$-approximate maximum weight is, in fact, similar to the 2-factor approximation that is easy for you to grasp. When the optimization problem is to minimize some (positive) quantity, such as the minimum traveling distance or minimum vertex cover, then a 2-factor approximate might appear. When the optimization problem is to maximize some (positive) quantity, such as the case here, then a $(1-\frac15)$-factor approximate might be expected.

You may want to take a look at the performance guarantees of approximation algorithm or even what is a bicriteria approximation algorithm?


Data structure for optimal deduplication of common subsets Consider a database with the following properties:

It stores symbols (represented as 64-bit integers) and sets of symbols
Sets may contain thousands of symbols, and there may be thousands of sets which are the same except for one or two added symbols
Every set should have exactly one canonical representation (two identical sets must have identical representations in the database)

If several sets contain large common subsets, they should be highly compressible: it should be possible to represent the common subset as a set itself, and store a reference to it, similarly to most persistent data structures.

However, the requirement for a single canonical representation of a set complicates things. Inserting certain new elements may rearrange the entire data structure, removing shared subsets. What kind of data structure would allow for shared common subsets in the majority of cases? My first guess is a balanced binary tree, but I'm not sure if balancing is even necessary; all that's needed is for the same set of symbols to always result in the same tree.

What you're looking for here is the intersection of two classes of data structures:

Persistent data structures, in which modifying a structure doesn't eliminate access to the old structure. This ensures that the shared parts don't have to be stored twice.
Uniquely represented data structures, as required by your "one canonical representation" phrase.

Unfortunately, most persistent balanced tree data structures are not going to be uniquely represented. One that is uniquely represented is the sorted Braun tree, but they do not share a lot of structure, and two trees with $O(1)$ differences can have structures that are different in $\Omega(n)$ locations.

If you nest Braun trees within Braun trees, you can get this down to $O(\sqrt{n \log n})$.

However, since your symbols are 64-bit integers, you're in a good spot. You can use path-compressed tries, which have a unique representation. They use $\Theta(n)$ nodes to store a set of $n$ symbols, and adding or deleting a symbol to an existing set of symbols allows sharing almost all of the original structure: no more than $2 + \min(n,w)$ new nodes are created, where $w$ is the word width (64 for you).


Removing edges from a fully connected weighted graph Given a fully connected graph $G(V,E)$ with associated edge weights and a set of constraints specifying distance $D(V_i, V_j) < M_{ij}$, where $\left\{V_{i..j}\right\} ⊂ V$, how can I go about finding the smallest subset graph $G'(V', E')$ such that none of the constraints are violated?

In other words, find the smallest subset of the graph such that the distance between a given set of vertices does not exceed some constant.

This is NP-hard by reduction from Set Cover.  The problem remains NP-hard even if edge weights are restricted to $\{1, 3\}$.

In the Set Cover problem, we are given a ground set $U$ containing $m$ elements $x_1, \dots, x_m$, a collection $\mathbf S$ of $n$ subsets $S_1, \dots, S_n$ of $U$, and an integer $k$, and our task is to determine whether there exists some set of at most $k$ of the $n$ sets in $\mathbf S$ whose union contains all $m$ elements in $U$.

First let's frame your problem as a decision problem: Given an edge-weighted undirected graph $G = (V, E)$, a set of $r$ constraints $d(v_{s(i)}, v_{f(i)}) \le M_i$ for $1 \le i \le r$ and an integer $q$, does there exist a subgraph $G'$ of $G$ such that each constraint is satisfied by some path in $G'$ and $G'$ contains at most $q$ edges?

To convert a given Set Cover instance into an instance of this problem:

Create a vertex $t$.
For each element $x_i$, create a vertex $u_i$ and the constraint $d(u_i, t) \le 2$.
For each set $S_j$, create a vertex $v_j$ and the unit-weight edge $v_jt$.
For each $x_i$ that belongs to a set $S_j$, create the unit-weight edge $u_iv_j$.
Add in all possible remaining edges, giving each weight 3.
Set $q$ to $m+k$.

First, suppose the solution to the Set Cover problem is YES.  It is easy to construct a solution to the constructed instance of your problem: For each set $S_j$ not selected by the Set Cover solution, delete the corresponding edge $v_jt$.  For each element $x_i$, choose some set $S_j$ such that $x_i \in S_j$ and $S_j$ was selected by the Set Cover solution (since the solution was YES, such an $S_j$ must exist) and keep the corresponding edge $u_iv_j$; delete all other edges incident on $u_i$.  Finally, delete all weight-3 edges.  Clearly this leaves exactly $m$ edges incident on $u$-vertices, plus at most $k$ edges connecting $v$-vertices to $t$, for a total of at most $q = m+k$ edges.  Each $u_i$ is connected to $t$ by a length-2 path via the vertex $v_j$ corresponding to its chosen containing set $v_j$, so all distance constraints are satisfied.  Thus the solution to the constructed instance of your problem is also YES.

Second, suppose that the solution to the constructed instance of your problem is YES.  Let $G'$ be any such satisfying subgraph.

Since $G'$ satisfies all distance constraints, and no weight-3 edge can participate in any such path, removing any remaining weight-3 edges in $G'$ must produce another valid solution $G''$.

Every $u$-vertex in $G''$ is adjacent to some $v$-vertex that is adjacent to $t$, since the answer to the problem was YES and there are no other paths from $u$-vertices to $t$ of distance $\le 2$.  Suppose some $u_i$ in $G''$ is incident on 2 or more outgoing edges.  All but one of these edges can be removed without violating the $d(u_i, t) \le 2$ constraint.  Let $G'''$ be the graph that results from performing these edge deletions on $G''$: $G'''$ is a valid solution.

Each of the $m$ $u$-vertices in $G'''$ is incident on exactly 1 edge, and since the answer to the problem was YES, the total number of edges in $G'''$ is $\le q = m+k$, so there are at most $k$ other edges in $G'''$.  These can only be edges between $v$-vertices and $t$.  Construct a solution to the original Set Cover problem by selecting the at most $k$ sets corresponding to the $v$-vertices that are adjacent to $t$ in $G'''$: clearly the union of these sets contains all $m$ vertices, so the answer to the original Set Cover problem is also YES.

We have established that a YES answer to each problem implies a YES answer to the other problem, so a NO answer to either problem implies a NO answer to the other one, so the problems are equivalent.  The constructed instance of your problem is easily constructed in polynomial time, so it follows that your problem is NP-hard.


Why does absence of strongly polynomial time algorithm for LP imply restriction to rational instances? From Bernhard Korte, Jens Vygen, Combinatorial Optimization,

  Instances of LINEAR PROGRAMMING are vectors and matrices. Since no
  strongly polynomial-time algorithm for LINEAR PROGRAMMING is known we
  have to restrict attention to rational instances when analyzing the
  running time of algorithms.

I was wondering why does the absence of strongly polynomial time algorithms for linear programming imply restriction to rational instances?

A strongly polynomial algorithm in the context of linear programming probably means an algorithm in the arithmetic model (where numbers can be added, multiplied, compared and so on), whose running time does not depend on the magnitudes of the numbers involved. Such an algorithm could be applied directly for real numbers. Examples of algorithms of this type are the simplex algorithm and the criss-cross algorithm, both really a collection of related algorithms. However, variants of these algorithm are either known not to be polynomial-time, or (in some cases) not known and not expected to be polynomial-time.

Other algorithms for linear programming exist: the ellipsoid algorithm and the interior-point algorithm (again, there are really many variants of these algorithms). The number of iterations in each case depends on the precision needed to guarantee reaching an optimal solution, and that's why they are not strongly polynomial. While these algorithms can also be implemented in the arithmetic model, convergence is no longer guaranteed to take polynomial time.

When the inputs are rational numbers, then the number of iterations needed to converge is polynomial in the length of the input, and therefore these algorithms become polynomial-time.


solving the recurrence t(n)=t(n-2)+d*(n^2)/2 with iteration method How can I solve $$T(n)=T(n-2)+\frac {d}{2}n^2$$
I couldnt find $d$ (dont know if I have to) and after 3 iterations I got to $k= \frac{n-1}{2}$
but had trouble to continue.

This answer assumes that $T(1) = \frac{d}{2}$

Your recurrence relation, in closed form, would be:

\begin{align}
T(n) & =  \frac{d}{2} n^2 + \frac{d}{2} (n-2)^2 + \frac{d}{2} (n-4)^2 + \dots + \frac{d}{2}\\
& = \sum_{i=0}^\frac{n-1}{2} \frac{d}{2}(n-2i)^2\\
\end{align}

Which, with little effort, can be simplified further:

$$\dots = \frac{d}{2} \sum_{i=0}^\frac{n-1}{2}n^2-4ni+4i^2
 = \frac{dn^2}{4}(n-1)
-2dn\sum_{i=0}^\frac{n-1}{2}i
+2d\sum_{i=0}^\frac{n-1}{2}i^2$$

For further simplification, you can use the facts that:

$$\sum_{i=1}^n i=\frac{n(n+1)}{2}$$

$$\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}$$

But I'll leave that to you.


Using Brzozowski's derivatives method to construct a minimal DFA so I am currently learning about dfa and nfa and i came across the following question which requires me to use Brzozowski's derivatives method to construct a minimal DFA recognizing the language defined by the rational expression below. I am having quite a bit of trouble understanding how Brzozowski's derivatives works and how I would apply it to the expression below. Could someone please show me step by step how I would do it alongside and explanation.

What seems to be the main problem is that I am not sure how to derive the derivative such as dR/da.

X = (aa + b)* ab (bb)*

The Brzozowski derivative of a language $L$ with respect to a symbol $a$ consists of all words $w$ such that $aw \in L$.

In your case, $L$ is the language generated by the regular expression $X$. Instead of solving your exact exercise, I will show how to compute the other Brzozowski derivative, with respect to $b$. A word generated by $(aa+b)^*ab(bb)^*$ has the form
$$ x_1 \ldots x_n ab (bb)^{2m}, $$
where $n \geq 0$, $x_i \in \{aa,b\}$, and $m \geq 0$. The only way that this can start with $b$ is if $n \geq 1$ and $x_1 = b$. Taking away $b$, we are left with
$$ x_2 \ldots x_n an (bb)^{2m}, $$
a collection of words which is described by the regular expression $(aa+b)^*ab(bb)^*$, the same one we started with.

Computing the derivative with respect to $a$ is slightly more complicated since there are two different cases, but I'll leave you to ponder that.

You might have also learned some rules for computing the derivative. In that case, you can compute the derivative by applying them mechanically.


What does a kernel of size n,n^2 ,... mean? So according to Wikipedia,

In the Notation of [Flum and Grohe (2006)], a ''parameterized problem'' consists of a decision problem $L\subseteq\Sigma^*$ and a function $\kappa:\Sigma^*\to N$, the parameterization. The ''parameter'' of an instance $x$ is the number $\kappa(x)$. A '''kernelization''' for a parameterized problem $L$ is an algorithm that takes an instance $x$ with parameter $k$ and maps it in polynomial time to an instance $y$ such that

$x$ is in $L$ if and only if $y$ is in $L$ and
the size of $y$ is bounded by a computable function $f$ in $k$.
Note that in this notation, the bound on the size of $y$ implies that the parameter of $y$ is also bounded by a function in $k$.

The function $f$ is often referred to as the size of
the kernel. If $f=k^{O(1)}$, it is said that $L$ admits a polynomial kernel. Similarly, for $f={O(k)}$, the problem admits linear kernel.
'''

Stupid question, but since the parameter can be anything can't you just define the parameter to be really large and then you always have linear kernel?

The point of investigating a parametrized problem is that we hope or assume that the parameter will be fairly small or even bounded by a known small constant in some particular case you encounter in practice. In that case, algorithms with FPT could be called efficient.
So yes, you can definitely pick an arbitrary parameter that will be very large in practice, but then a linear kernel will probably not be useful, because you are measuring the wrong parameter.
As a side remark, this is not something specific to parametrized complexity. In any type of complexity, you must be careful that the thing your are investigating the complexity of is actually meaningful.


HandyAR finger tip detection and tracking I am reading this paper Handy AR.

As suggested I am adding certain quotes from paper to get basic idea of what is it about :

Intro

  In this paper, we present and evaluate a method to use a
  user’s bare outstretched hand in the same way a cardboard AR
  marker would be used, enabling spontaneous tangible user interfaces
  in mobile settings

Steps:

Adaptive Hand Segmentation

  Given a captured frame, every pixel is categorized to be
  either a skin-color pixel or a non-skin-color pixel. An adaptive
  skin color-based method 17 is used to segment the hand
  region. According to the generalized statistical skin color
  model 14, each pixel is determined to be in the hand region
  if the skin color likelihood is larger than a constant threshold.
  In order to adapt the skin color model to the illumination
  change, a color histogram of the hand region is learned for
  each frame and accumulated with the ones from the previous
  n frames (n = 5 works well in practice). Then the probability
  of skin color is computed by combining the general skin
  color model and the adaptively learned histogram.

Accurate Fingertip detection

  Fingertips are detected from the contour of a hand using a
  curvature-based algorithm similar to the one described in [2].
  We then fit the curvature points to ellipses in order to increase
  the accuracy. The curvature of a contour point is measured on
  multiple scale levels in order to detect fingertips with various
  sizes as follows: The points with higher curvature values than
  a threshold (on any scale level) are selected as candidates for
  fingertips.
  Since the detection algorithm may produce false positives
  of fingertips for initial detection, we choose the most frequently
  detected points above the center of the hand for a
  certain number of consecutive frames as our final fingertips.
  Thus, for initial detection, the hand has to be held fingers
  up, which is the most convenient and by far the most common
  pose anyway. After fingertips have been detected, we
  eliminate false positives by tracking a successful configuration
  over time.

FingerTip Tracking

  Once fingertips are detected, we track them based on
  matching the newly detected fingertips to the previously
  tracked fingertips. Similar to 21, we track the fingertip trajectory
  by a matching algorithm that minimizes the displacement
  of pairs of fingertips over two frames. In addition, we
  use our knowledge about the centroid of the hand blob to effectively
  handle large movements of the hand as follows: The
  matching cost is minimized as the formula I mentioned below.

I have a couple of doubts in this :
1. In the 2nd paragraph of the 2nd points of steps:

  After fingertips have been detected, we
  eliminate false positives by tracking a successful configuration
  over time.

What does 'successful configuration over time' mean?
If we already are tracking a successful configuration , then why are there false positives.

2.In the next section, Fingertrip tracking has been explained. From what I understood , it has two parts

Using a matching algorithm
Using centroid to effectively handle large movenments.

My doubt is in the second part, I am not able to understand properly how does it handle large movenments and also the correctness proof of that statement.

Formula for fi+1

where fi fi+1 are the sets of N fingertips at the ith and
i + 1th frame and
 Ci , Ci+1 are centroids at ith and i + th frame.

Citation -

I got this from 1 paper published by Taehee Lee, Tobias Hollerer in 2007 11th IEEE International Symposium on Wearable Computers

Handy AR

What does 'successful configuration over time' mean?...  why are there false positives.
I am not able to understand properly how does it handle large movements

they are repeatedly scanning a similar form, the "hand blob", so any outliers from the usual successful input will hopefully be ignored. (maybe if someone nearby passes you something and it thinks their hand is yours for a few frames)

the paper says they register the "hand blob" or centroid of skin color as an easier tracking target for large movements. the "one time calibration" is probably about where your hand is, and it's predominant shade, in relation to the device. then it makes sure the fingers are there and orientates using the thumb. there is no difference to the formula for large movements except where Ci+1 actually is compared to Ci.

I really am looking forward to real time interaction with augmented reality.
are there many more papers you know of like this? id love to read them too.

Edit: hello again raphael.  this is someone of my lvl of understanding and the attempt has been made to fill all of the exceedingly strict criteria for a simple question. this guy is interested, like many are, but has been told off and deleted by you lot before. i can tell.


Do $s$-$t$ cuts partition contingent vertices? The definition of an $s$-$t$ cut is a partition of the set of vertices $V$ into $2$ sets $(A, B)$ with $s$ in $A$ and $t$ in $B$. My understanding of set partitions is that the positioning of elements in the graph does not matter.

However, if this is the correct notion of partitioning, then can construct a pathological example. Consider the following network. $$s \to B_1 \to A_1 \to B_2 \to A_2 \to t.$$Let each of the edges have a capacity of $1$. Then the max flow is clearly $1$. If we let the $s$-$t$ cut be such that set $A$ consists of $s$, $A_1$ and $A_2$, and $B$ is the rest, then the capacity of the cut is $3$ since there is a flow of value $1$ exiting each of the $3$ vertices in $A$. This contradicts the max-flow-min-cut theorem.

Is my understanding right then that the $s$-$t$ cut is not a partition of a set but a graph? By this I mean, that the resultant two sets have to be contiguous?

The example is correct: in this $s$-$t$ cut the capacity of the cut is indeed $3$. However, the min-cut in the max-flow min-cut theorem talks about the capacity of the minimum $s$-$t$ cut. So one must take an $s$-$t$ cut that gives minimum capacity: what you have in your example is not one of them.


Traveling Salesman's Tour Approx Algorithm: is this really a Hamiltonian Path? I'm given this problem:

Consider the following closest-point heuristic for building an approximate traveling-salesman  tour. Begin with a trivial cycle consisting of a single arbitrarily chosen vertex. At each step, identify the vertex u that is not on the cycle but whose distance to any vertex on the cycle is minimum. Suppose that the vertex on the cycle that is nearest u is vertex v. Extend the cycle to include u by inserting u just after v. Repeat until all vertices are on the cycle. Prove that this heuristic returns a tour whose total cost is not more than twice the cost of an optimal tour.

This is the same as Prim's algorithm.  Unless I'm missing something, this is not an approximate traveling salesman tour since the traveling salesman requires a Hamiltonian path where we don't revisit any nodes, but on many graphs this algorithm seems to require revisiting nodes to get back to the source node.  Am I wrong or is this problem unclearly worded?

You're wrong and the question is also unclearly worded. First, TSP is usually defined in terms of Hamiltonian cycles, not paths. That is, the salesman is in each city exactly once, except for the start point, which he is in twice. Second, as @avakar explains in his first comment, the algorithm given doesn't repeat vertices.

Also, the question seems to be making an unstated assumption. To flesh out @avakar's second comment, suppose you are given cities $1, \dots, n$ where:

$d(i,n)=k$ for $i< n-2$
$d(n-2,n)=d(n-1,n)=2$
$d(n-2,i)=d(n-1,i)=0$ for $i<n$
$d(i,j)=1$ for all other pairs $i$,$j$.

The optimal tours have cost $n$: e.g., $1, 2, \dots, n-2, n, n-1, 1$. However, the given algorithm will produce a tour like $1, n-1, n-2, 2, 3, \dots, n-3, n, 1$ when started at any vertex except $n$.  This has cost $n-5+2k$, which is more than twice the optimum whenever $k>\tfrac12(n+5)$.