Expected gain of a game of chance with differently-priced tokens Foo and Bar are playing a game of strategy. At the start of the game, there are $N$ apples, placed in a row (in straight line). The apples are numbered from $1$ to $N$. Each apple has a particular price value.

The price of $i$th apple is $p_i$.

In this game, the players Foo and bar make an alternative move.

In each move, the player does the following:

If there is more than one apple left, the player tosses an unbiased coin. If  the outcome is head, the player takes the first apple among the apples that are  currently present in a row in a straight line.
If there is a single apple left, te player takes it.

The goal here is to calculate the expected total price value that Foo will get if Foo plays first.

Example 1:
N=5
Apple price val:
5 2 3 1 5

Answer is : 11.00

Example 2:
N=6
7 8 2 3 7 8

Answer : 21.250

Example 3:
N=3
1 4 9

First           Second      Third          Foo Total Val
Foo gets 1  Bar gets 4  Foo gets 9          10
Foo gets 1  Bar gets 9  Foo gets 4          5
Foo gets 9  Bar gets 1  Foo gets 4          13
Foo gets 9  Bar gets 4  Foo gets 1          10

probability 0.5 • 0.5 = 0.25.
Expected value (Foo)= (0.25 *10 )+ (0.25 *5) + (0.25*13)+ (0.25*10) = 9.500

I wrote the following code:

#include<iostream>
using namespace std;
double calculate(int start,int end,int num,int current);
int arr[2010];
int main()
{
    int T;
    scanf("%d",&T);
    for(int t=0;t<T;t++)
    {
        int N;
        scanf("%d",&N);
        for(int i=0;i<N;i++)
        {
            scanf("%d",&arr[i]);
        }
        printf("%.3lf\n",calculate(0,N-1,N/2+N%2,0));
    }

    return 0;
}
double calculate(int start,int end,int num,int current)
{
    if(num==current)
        return 0;
    double  value=0;
    value=.5*arr[start]+.5*arr[end]+.5*calculate(start+1,end,num,current+1)+.5*calculate(start,end-1,num,current+1);
    return value;
}

But the above code is quite slow. The constraints are: price of apples $p_i \le 1000$; $1 \le N \le 2000$; there are 500 test cases. How can I solve this more efficiently?

They probably meant you to solve it using dynamic programming. Since I'm guessing this is an exercise, I won't say anything more on this front. Also, your program is incorrect: it doesn't consider the actions of Bar.

The game is not really a game of strategy, since there are no choices involved, only chance. In order to compute the expected value that Foo gets, it is enough to compute the probability that Foo takes each particular item. Let $p_{a,b}$ be the probability that Foo takes an item which is the $a$th from the left, $b$th from the right ($a,b \geq 0$, total number of elements is $a+b+1$). Then
$$
\begin{align*}
p(0,0) &= 1, \\
p(0,1) &= 1/2, \\
p(1,0) &= 1/2, \\
p(1,1) &= 1/2, \\
p(0,b+2) &= 1/2 + p(0,b)/4, \\
p(a+2,0) &= 1/2 + p(a,0)/4, \\
p(1,b+2) &= p(0,b+1)/2 + p(1,b)/4, \\
p(a+2,1) &= p(a+1,0)/2 + p(a,1)/4, \\
p(a+2,b+2) &= (p(a+2,b)+2p(a+1,b+1)+p(a,b+2))/4.
\end{align*}
$$
You could precompute the requisite values for $a+b+1 \leq 2000$ and then your program will be blazingly fast.

It turns out that for fixed $c$, $p(c,n-c)$ tends to a limit $p_c = 1/2(1 + (-1)^c/3^{c+1})$. To see why, note first that $p_0$ is the ability that if you and a friend alternate tossing fair coins, yours will come up HEAD first. There are many ways to see that $p_0 = 2/3$. Next, we have the formula $p_{c+1} = p_0 (1-p_c) + (1-p_0) p_c$ (exercise), from which the formula for $p_c$ follows by induction.


Can DFA with output (definition?) match expressiveness of NFA with unique output? For a deterministic finite automaton (DFA), some output tasks are easy when done in one direction, but difficult (or impossible?) when done in the reverse direction. Let's take a simple example of outputting a word lower-case, or upper-case, depending on a control sequence included in the input. So the task

l:aNNa should become anna
u:aNNa should become ANNA

(where aNNa could be an arbitrary long word) seems to be quite easy for a DFA with output. The task in the reverse direction

aNNa:l should become anna
aNNa:u should become ANNA

however seems to be impossible for a DFA with output, at least for the commonly encountered definitions of DFA with output. On the other hand, a nondeterministic finite automaton (NFA) with unique output  has no problems doing a task in the reverse direction, if it can do it in one direction.

Is the observation correct that a DFA with output can't do the task in the reverse direction, if it is forced to consume its input one symbol at a time?
Would it be possible to relax the restrictions for DFA and NFA, such that a NFA (with unique output) would not gain any additional expressiveness from the relaxed restrictions, but the DFA with output (for the relaxed restrictions) would be able to match the expressiveness of a NFA with unique output?

An interesting definition can be found in an old survey article by J. Berstel and J. Sakarovitch

  A plurisubsequential function is a finite union of subsequential functions having pairwise disjoint domains. A subsequential function is a function realized by a gsm equipped with an additional partial output function $\rho$ defined on the states of the gsm. ...1

The finite union with pairwise disjoint domains covers cases like above, where more than one output makes sense, but we know only later which. An reasonable implementation could first scan the input once, determine the relevant subsequential function, and then compute that function by a second scan over the input.

The survey proves that addition of one is a plurisequential functions if the digits of the number are given in low-ending order, but not if the digits are given in big-endian order. So the observation from the question about the reverse direction is correct.

Interesting, J. Berstel also wrote a book which contains an answer to the question whether it is possible to relax the restrictions for DFA with output such that it matches expressiveness of NFA with unique output. From
J. Berstel, Transductions and context-free languages Chapter IV, 5 Bimachines

  Definition A bimachine $\mathfrak B = \langle Q, q_-, P, p_−, \gamma\rangle$ over $A$ and $B$ is composed of two finite sets of states $Q,P$, two initial states $q_− \in Q$, $p_− \in P$, of two partial next state functions $Q \times A \to Q$ and $A \times P \to P$ denoted by dots, and a partial output function $\gamma : Q \times A \times P \to B^∗$.

The output of such a machine is naturally partitioned into as many parts as the input has symbols, some of these parts can be empty. To compute the $i$-th part, $Q$ processes the first $i-1$ input symbols forward, $P$ processes the last $n-i-1$ input symbols backward, and $\gamma$ computes the output from the $i$-th input symbol $a$ and the current states $q$ and $p$ of $Q$ and $P$ as $\gamma(q,a,p)$.

A partial function is rational if and only if it is realized by a bimachine. Bimachines were introduced by Schützenberger in 1961. In 2006, J. Rhodes organized a P vs NP Workshop, and where Pedro V. Silva gave an introduction to bimachines.

A bimachine has only a finite number of states and is deterministic, but in general it needs $O(n)$ forward and backward scans over the input. The plurisubsequential functions (or slight extensions of this idea) are attractive, because they only need two forward scans over the input.

  1 ... If a computation in the gsm ends in some state, then the word associated with that state by the function $\rho$ is concatenated at the end of the output, provided p is defined for this state. Otherwise, it indicates that the computation is unsuccessful, and therefore that the function realized by this transducer is undefined for the given input.


Subtyping and subkinding, are they relevant? I'm thinking about a type system that has some special kind of some certain types that are subtypes of the universe kind type.

Imagine the typing relation, where $A$ and $B$ are both types, $\textbf{Type}$ is the universe kind, like * in Haskell or Type in Idris or Set in Agda; while <: denotes subtyping:

$$
A:a \\
B:b \\
A <: B \\
a <: \textbf{Type} \\
b <: \textbf{Type}
$$

Then what should the relation between $a$ and $b$? Could one of them be the subtype (or subkind?) of the other? Although it is fine to make $a$ and $b$ distinct, but ideally we want more consistent subtyping (subkinding) relations to present.

In other words, if I allow either $a <: b$ or $b <: a$, will the type system become inconsistent?

There will be no inconsistency. Those arise from shady postulates which state that some subkind is an element of itself, or that "too large" a kind/type is an element of a "too small" one (the most famous example is $\mathrm{Type} : \mathrm{Type}$), but that is not what we are dealing with here.

To give an example of what you're looking for, take $\mathrm{Type}$ to be the class of all sets. For the subtype and subkind relations we simply use subset and subclass inclusion. Take $a$ to be the class of all finite sets, and $b$ the class of all countable sets. Let $A = \{23, 42\}$ and $B = \mathbb{N}$. Then we have $A : a$, $B : b$, $A \subseteq B$, $a \subseteq b$, and both $a$ and $b$ are subkinds of $\mathrm{Type}$. And it would not be difficult to arrange $A \subseteq B$ and $b \subseteq a$, if we so wished.

Or you could take $\mathrm{Type} = a = b$ and $A = B$, but that's not a very informative answer, even though it has its virtues.


Shortest path algorithm where the path can travel through at most 2 vertices in X ⊂ V I am trying to model a problem to enable me to use Dijkstra's Shortest Path algorithm. Given are a set of vertices V, and a set of vertices X ⊂ V.
Between these vertices are given a set of edges where:

edge(u,v) with u ∈ V \ X being weighted > 0
edge (u,v) where u ∈ X being weighted = 0
other edge combinations (i.e. u,v ∈ V and u,v ∈ V \ X) are allowed, but follow the same rules as above

At most two vertices ∈ X are allowed to be visited in the path.
How can this be modeled as a shortest path algorithm problem? I've seen solutions for at most one vertices ∈ X are allowed by splitting the graph into two copies but that doesn't quite hit my requirements.
Any help much appreciated!

You never say what the goal is. I suspect that you want to find the shortest a path from a given vertex $s$ to a given vertex $t$ that passes through at most two vertices in $X$.
In this case you can assume w.l.o.g., that $s,t \not\in X$. Moreover, you can assume that the input graph is directed. If this is not the case, then  you can preliminarily replace each undirected edge $\{u,v\}$ with the two directed edges $(u,v)$ and $(v,u)$.
Let $G=(V,E)$ be the input graph and let $F = \{ (u,v) \mid u \in X\}$ be the set of outgoing edges from some vertex in $X$. Make a new graph $H$ containing three copies $G_1, G_2, G_3$ of the graph $(V, E \setminus F)$.
Then, augment the graph as follows:

For each edge $(u,v) \in F$ add:

an edge (of weight $0$) between the copy of $u$ in $G_1$ and the copy of $v$ in $G_2$.
an edge (of weight $0$) between the copy of $u$ in $G_2$ and the copy of $v$ in $G_3$.

Add a new vertex $t^*$ and the three edges (of weight 0) between each copy of $t$ in $G_1$, $G_2$, and $G_3$ and $t^*$.

You can now find a shortest path $P$ between the copy of $s$ in $G_1$ and $t^*$.
The list of vertices traversed by $P$ (except for the final vertex $t^*$) will induce the sought shortest path on $G$.


Implications of the $\Omega(\frac{2^n}{n})$ circuit lower bound being tight There is a basic result in circuit complexity that says:

  There exists a language that cannot be solved with circuits of size $o(\frac{2^n}{n})$.

The argument is a simple counting argument on the number of boolean functions and the number of distinct circuits.  See, for example, these lecture notes.

I believe it is unknown whether or not this bound is tight.  That is, we don't know if the following statement is true:

  Every language can be solved with circuits of size $O(\frac{2^n}{n})$.

If this statement were true, would it have any interesting implications for complexity theory?

This has been proved by Muller as early as 1956. Here is the construction. Let $k$ be a parameter. We first compute all possible functions on the first $k$ inputs in size $O(2^{2^k})$ (see below). We then construct a decision tree for the other $n-k$ variables, connecting it to the correct function on the remaining variables. This takes $O(2^{n-k})$ (see below), for a total of $O(2^{2^k}) + O(2^{n-k})$. Choosing $k = \log (n - \log n)$, we obtain the desired bound.

We compute all possible functions on $k$ inputs inductively. Let $Z_k$ be the size of a circuit computing all possible functions on $k$ inputs. There are two functions on zero inputs, so $Z_0 = 2$. Every function $f(x_1,\ldots,x_k)$ on $k$ inputs can be written as $x_k f(x_1,\ldots,x_{k-1},1) + \overline{x_k} f(x_1,\ldots,x_{k-1},0)$, so $Z_k = Z_{k-1} + 2^{2^k} \cdot O(1)$. The solution of this recurrence is $Z_k = O(2^{2^k})$.

In order to compute the decision tree, we use a similar construction: given a tree $T$ for the first $k-1$ variables, we can construct a tree for the first $k$ variables of the form $x_k T + \overline{x_k} T$. The recurrence we get is $W_k = 2W_{k-1} + O(1)$, whose solution is $W_k = O(2^k)$.


Data structure for testing all subsets of a query for membership Is there a data structure that efficiently supports the following operations?

Add set
Query whether any subset of a set has been added.

This could be implemented with linear overhead by testing every added set during every query. Can it be implemented more efficiently? Small probabilities of false positives/negatives are acceptable (e.g. Bloom-filter style).

Let's say all your sets are finite subsets of $\mathbb N$. Let $S\subseteq \mathcal P( \mathbb N)$ denote your set of sets.

You want two operations:

$O_1(S,s')$: For any $s'\subseteq \mathbb N$, add $s'$ to $S$
$O_2(S,s')$: For any $s'\subseteq \mathbb N$, is there some $s\in S$ so that $s\subseteq s'$?

Here are a few ideas to speed things up:

You're going to test if a set if a subset of another a lot so you should probably keep the size $|s|$ of each set $s$ available in $O(1)$ so that when you need to test if $s\subseteq s'$, you start by checking if $|s|\le |s'|$ and if not, you can return false right away. And it you indeed have $|s|\le |s'|$, then you just run the normal slow test.
Note that if you have $s_1\in S$ and $s_2\in S$, so that $s_1\subseteq s_2$, then if $s_2\subseteq s'$, you also have $s_1\subseteq s'$. So you don't need to keep $s_2$ in $S$ for $O_2$. So you can represent $S$ by a set of sets so that $s\in S$ and $s\subsetneq s'$ implies $s'\not \in S$.  In other words, you only need to keep track of the sets in $S$ that are minimal for inclusion. This can be implemented pretty efficiently: When adding a set $s'$, for all sets $s\in S$ so that $|s|\le |s'|$ (ordered by increasing cardinal), if $s\subseteq s'$, then don't add $s'$ because it won't be minimal (or is already in $S$). Otherwise, add $s'$ and then among sets $s\in S$ so that $|s'|<|s|$, remove those so that $s'\subseteq s$ (because they are no longer minimal).
Keep a set $t$ that's equal to the union of all sets in $S$. Then, instead of running $O_2(S,s')$, you can run $O_2(S,s'\cap t)$ instead (because if for some $s\in S$, $s\subseteq s'$, then since $s\subseteq t$, $s\subseteq s'\cap t$ and, if $s\subseteq s'\cap t$, then $s\subseteq s'\cap t \subseteq s'$).

With these ideas in mind, I'd represent $S$ by a dictionnary (implemented as a doubly linked list of pairs $(key,value)$ with the keys in increasing order) $d$ so that $d(k)$ is a doubly linked list containing exactly the minimal (for inclusion) sets in $S$ of cardinal $k$.

O1(S,s')
  if O2(S,s')
    return
  if d(k) doesn't exist
    d(k) := new_doubly_linked_list()
  add(d(k),s')
  S.t := union(S.t, s')
  for each key k of d so that |s'|+1 <= k
    for s in d(k)
      if subset(s', s)
        remove s

_O2(S,s')
  for each key k of d so that k <= |s'|
    for s in d(k)
      if subset(s,s')
        return true
  return false

O2(S,s')
  return _O2(S,inter(S.t,s'))

(Notice that even though I didnd't do it explicitely in the code of O1, you can do a single traversal of the doubly linked list representing d)

I don't think this improves too much in the worst case but in average it should.


Correctness of splitting an undirected tree into a forest of trees with even number of children Given an undirected tree (i.e. a tree without any designated root) of even number of nodes.
The task is to remove as many edges from the tree as possible to obtain a forest of trees,
where each such tree contains even number of nodes.
And return/output number of removed edges as an output/answer.

Counting maximum number of removed edges is relatively simple:

Choose any node as a root node;
Recursively traverse a tree using depth-first approach;
Count number of children of each sub-tree (from bottom to up),
and cut sub-tree from the tree if this sub-tree has even number of children (i.e. simply increment counter of removed edges);

This solution is correct but I don't understand why.

I would like to see proof of correctness of such algorithm.

In particular, I have the following doubts (when I'm thinking on this solution):

Why starting DFS from any chosen root gives correct maximum number of removed edges?
Why cutting sub-trees with even number of children from bottom to up gives correct result?

I wrote on paper all possible configurations 1, 2, 3, 4, 5, 6-nodes of undirected trees.

For example, there are two possible configurations of undirected tree with 4 nodes:

(a)

x-x-x-x

(b)

x-x-x
  |
  x

In (a), you can split a tree into 2 sub-trees with 2 nodes each.

In (b), you can not do it since it will be two sub-trees of odd number of nodes (with 1 node and with 3 nodes respectively).

So my doubts based on suggestions:

What if it depends where you start cutting sub-trees?
What if greedy cutting sub-trees with even number of children from bottom to up doesn't give correct maximum number of removed edges? (continue of first question)

This puzzle is described on HackerRank as "Even Tree".
Their editorial and discussion just declared algorithm but they don't say why it works.
Also, I found discussion on stackoverflow but they also don't give explanation why such approach works.

I got my "Aha! Gotcha" moment when I changed my point of view from nodes (as root of a subtree) to edges. Let me explain.

The set of edges that can be cut is a "static property", the set of choices is not changed by the earlier cuts that have been made. Any edge is considered to be "even" if on both sides it has an even number of nodes in the tree. Clearly we can only cut even edges. But also, cutting an even edge does not change the even property of the remaining edges, as we merely remove an even number of nodes in subtrees.

So, we are set to find the even edges, and we will cut them all. The proposed solution uses DFS, but any decent traversal will do I would think. The property that a subtree has an even number of nodes now means (in my terminology above) that the edge outside leading to the root of the subtree is in fact even.


If we say L ⊂ {a, b, c}* then is L an infinite language? I wonder if we say L ⊂ {a, b, c}* then is L an infinite language?
I think Kleene star makes me think L is an infinite language.

$L$ is not necessarily an infinite language. $\{a,b,c\}^*$ is an infinite language, but you've written $L\subset\{a,b,c\}^*$, and infinite sets can (and do) have finite subsets. Consider $L=\{a\}$, then $L\subset\{a,b,c\}^*$ but $\lvert L\rvert=1<\infty$


GATE CSE 2009, Which of the following is FALSE? This is a question from GATE CSE 2009.

Which of the following is FALSE?
A]  There is a unique minimal DFA for every regular language.
B]  Every NFA can be converted to an equivalent PDA.
C]  Complement of every context-free language is recursive.
D]  Every non-deterministic PDA can be converted to an equivalent
deterministic PDA.

The answer provided to me (without any explanation) is B, which I think is wrong.
Here is my approach.

A] Every RL has an equivalent DFA and there is one unique minimal DFA
for a given RL. [so True]
B] Since RL are proper sub-set of CFL and every RL has equivalent FA
and every CFL has equivalent PDA, every FA can be converted to PDA but
not vice versa. [so True]
C] Given a CFL we can create an equivalent Total TM [RECURSIVE],
RECURSIVE languages are closed under complement. [so True]
D] This is only remaining option and by method of elimination answer.

Is my answer correct?

A is true, but I don't find your argument convincing (it simply restates the claim). See this question for example.
B is not the correct answer to this problem, because as you say it's true. Your reasoning isn't very formal though, and swaps some reduction orders. A correct reduction would be NFA → (superset construction)→ DFA → (trivial) → PDA.
C seems fine to me.
D is indeed left over, and is indeed false. Inherently ambiguous context-free languages can be recognized by nondeterministic PDAs, but not by deterministic PDAs.


Algorithm for breaking a graph into sub-graphs based on an attribute I am a biologist doing some computational work. I encountered a problem and need some help since I don't have much algorithmic background.

The problem:
Assume we have a non-directed, weighted graph, in which every node has some categorical attribute, e.g. color. I want to break the graph into sub-graphs in which there is at most one node of each color. Decisions should be made by trying to preserve the strongest connections (edges with highest weights). For example, let's look at the graph below (I didn't include weights as this would be hard to see):

In this case, I would like to break the graph into two sub-graphs (assuming that this is what the weights indicate):

Two notes (I don't know if they matter though):

The maximal number of colors is known in advance
After the graph was broken, I don't really care about the topology anymore - I just want to know which nodes ended up together.

My questions:
My first question is: does this look familiar to you? Has this problem been solved before? Maybe it's a variant of something every CS student learns? If so, can you please refer me to relevant information/literature?
If not, Then I'd like some help on how to approach this. Can you give some ideas on how to start developing and algorithm that can solve this type of problem?
Any other advice would be useful. Thank you!

This seems to be the "minimum weight orthogonal partition problem", which has been studied among others by Zheng et al. [1]. Computer scientists have also studied it under the name "colourful components", though it sometimes refer to an unweighted variant. The problem is known to be NP-hard, and some approximations exist [2]. There are probably more recent results, these two references should help you find them.

[1]: Chunfang Zheng, Krister M. Swenson, Eric Lyons, David Sankoff:
OMG! Orthologs in Multiple Genomes - Competing Graph-Theoretical Formulations. WABI 2011: 364-375 -- http://albuquerque.bioinformatics.uottawa.ca/kms/files/papers/2011-ZhengOMG.pdf

[2]: G. He, J. Liu and C. Zhao: Approximation Algorithms for Some Graph Partitioning Problems. Graph Algorithms and Applications 2, pp. 21-31 (2004) -- https://www.researchgate.net/publication/220639657_Approximation_Algorithms_for_Some_Graph_Partitioning_Problems


Edge exchange property of two Minimum Spanning Trees Given an undirected graph G with weight on its edges and 2 different minimal spanning trees(MSTs): T, T'
Then I want to prove the following:

For every edge e in T that's not in T', there is an edge e' in T'
that's not in T such that if we replace e with e' in T (let's call
it T_new) then it's still a minimal spanning tree of G.

I think I am too close for finding the right algorithm but stuck a little:

I have proved that weight(e) must be exactly equal to weight(e').

Since T is a tree, deleting e will result in 2 separated components, then for T_new to be a tree it must use one of the edges connecting two vertices from those different components.

But, I wasn't able to know which edge e' exactly will work. Plus I wasn't able to prove that always there is such an edge (I just found some requirements for e' that is must satisfy).
Some notes: I know Kruskal algorithm, and familiar with an algorithm in which we can paint some edges in yellow and request it to generate minimal spanning trees with maximum yellow edges (In other words from all found minimal spanning trees return the one with maximum number of yellow edges)

Here is a proof. Let $V$ be the vertices of $G$. $V$ are also the vertices of $T$ and the vertices of $T'$.
If $e$ is deleted from $T$, we will get two trees. Let the vertices of these two trees be $(V_1, V_2)$, which is a cut of $V$.
Since $T'$ is a tree, if we add $e$ to it, we will obtain a cycle. Since that cycle crosses $(V_1, V_2)$ at $e$, it must cross $(V_1, V_2)$ at another edge, say, $e'\in T'$.

Since $T \setminus \{e\}\cup \{e'\}$ is a spanning tree of $G$ and $T$ is an MST,  $\text{weight}(e) \le \text{weight}(e')$.
Since $T' \setminus \{e'\}\cup \{e\}$ is a spanning tree of $G$ and $T'$ is an MST,  $\text{weight}(e') \le \text{weight}(e)$.

So, $\text{weight}(e) = \text{weight}(e')$.
$T \setminus \{e\}\cup \{e'\}$, which is a spanning tree of the same weight as $T$,  must be an MST of $G$. $\quad\checkmark$


Can a type system serve as a proof assistant for foreign functions? Given that:

A language with very expressive type systems (e.g. Idris) can also have escape mechanisms like foreign function interfaces/unsafePerformIO.
There are proof assistants that can be used to prove some properties of a program written in a language that doesn't have a type system capable of expressing those properties.
The Curry–Howard correspondence shows that a successfully type-checked implementation of a function with a given type is proof of what is expressed by that type.

Can one express non-trivial proofs of some property of foreign language code in the type system of the native language?

For example, pretend I have a C function called stable_qsort that sorts numbers in a terribly clever and efficient way while maintaining the order of already equal elements, and an Idris program that calls stable_qsort via its FFI, but I don't trust this relatively obscure C function. Could I prove that the function doesn't reorder equal elements, for all inputs, in my Idris code instead of using a separate proof assistant?

Long story short: no you can't. A foreign function is like a black box and the type you ascribe to it is a promise you make: in the Curry-Howard correspondence that would correspond to adding an axiom to your theory.

That being said, there are ways. In Coq for instance, there are various formalisations of the C standard (e.g. Robbert Krebbers' work). Because you have an explicit representation of C programs and their semantics, you can write your code directly in the proof assistant and it is then possible to prove some of its properties.


How are threads implemented in different OSs? I was reading Linux Kernel Development by Robert Love, where I came across this

  Linux takes an interesting approach to thread support: It does not
  differentiate between threads and normal processes.To the kernel, all
  processes are the same— some just happen to share resources.

I do not know much about OSs (aspire to know more) and kernels and hence the above quote raised a question about thread implementations in different OSs(at least the popular ones like Windows, Linux and Unix).

Can someone please explain the different techniques for providing thread-support in an OS? ( and optionally contrast them)

Threads and processes are execution contexts.  They mostly differ only by the amount of shared state (memory, signal handlers, file descriptors,...) with the other execution contexts (processes share little with other processes; threads share a lot with the other threads in the same process).

Most OS keep the two things separated, and thus know about several kinds of execution context.

Linux kernel on the other hand has just one kind of execution context, which is able to share or not things with other. If you want a process, set it up so that it share little, it you want threads, set them up so that they share what they need. You can set things up so that they behave in a way unsuitable for the process/thread terminology.

The POSIX API commonly used when programming for Linux knows only about processes and threads and thus most programs don't really care about what is an implementation detail for them in the way responsibilities are divided between kernel and user space. Older implementations of threads leaked some the implementation details (ps showing threads, thread id and process id mixing up, ...) and didn't provide exact POSIX semantic in some cases (signal delivery was problematic IIRC).


Solomonoff's theory of induction, Kolmogorov complexity and Bayesian Inference My motivations for asking this question are philosophical in nature. I'm by no means a computer scientist though, and I feel as though this question should be answered by someone who is since it's one thing to read about a subject second hand and another to understand it first hand. I'm an A-level student of philosophy, physics and mathematics (UK qualification) if that helps you formulate an answer at all.

The question relates to the problem of induction in that, we have little reason to believe the universe is uniform and apply that expectation to science and inference. However, I've seen the claim made that this guy Solomonoff created a theory of induction that uses a Bayesian framework as well as something called 'Kolomogrov complexity' as an objective measure of 'complexity' in a model or hypothesis. For example, if we observe over and over again that all A's are B's, we might be tempted to formulate the hypothesis:

"All A's are B's",

This would be afforded the maximum credence from a bayesian framework since it predicts that A's are B's with a probability of 1 and we're attaching ourselves to the likelihood lover's principle. However, you could also formulate the hypothesis:

"All A's are B's until a time t where they are C."

And there are infinitely many of these hypothesis since the 'C' can represent literally anything. This has a bayesian multiplier equal to the previous hypothesis so technically have an equal credence if we don't prefer one of these in our priors. And the only way (it would seem) to decide between the two is to see if hypothesis 2 shows it's prediction at time t. So we would otherwise have to always wait until time t to see if hypothesis 1 is correct.

My question can be split up into three parts:

1) Is "Kolmogrov complexity" generally considered a genuine formulation of an objective definition for complexity/simplicity?

2) Would the former hypothesis, with such an understanding of complexity be considered more 'simple'?

3) How would this understanding of complexity be used practically when distinguishing between hypotheses? Or is it just obvious that the former type of hypothesis is more simple?

Although this is really a philosophical question, I suppose I would also like to know if anyone here has any ideas about why we should prefer more simple hypotheses. And perhaps, how would you increase your bayesian prior probability given some measure of complexity for a hypothesis?

Thank you in advance for any answers.

Mathematics and computer science doesn't have anything to say about whether simpler hypotheses are more likely.  That's a question about reality, not about math / computer science.

What computer science can provide is the notion of Kolmogorov complexity.  Kolmogorov complexity is one reasonable notion of simplicity: bit-strings with lower Kolmogorov complexity are "simpler" in some sense.

Now we could start with a model of reality, which says that nature randomly picks a process for generating data; the process is obtained by picking a Turing machine at random, with smaller (simpler) Turing machines more likely to be chosen than complex ones; and then nature runs the Turing machine and the data you observe is the output of that Turing machine.  That's a sketch of a possible model of reality; basically, it's an assumption about how nature works.

That assumption then implies (if we fill in some details) a particular prior on hypotheses.  A hypothesis amounts to a Turing machine.  There will be multiple Turing machines that are all consistent with the observations (that could have produced those observations), and Bayes theorem + the prior will let you infer the posterior distribution on which of those hypotheses are most likely.

This is a possible way to obtain a prior, and it seems reasonable to me.  Computer science can't tell you whether that model (that assumption) is a good model of reality. But it can help you work out the consequences of making that assumption.

Finally, you seem to be asking why simpler explanations are more often correct.  Basically, why is Occam's razor useful?  I don't know if there is any completely convincing answer to that.

One possible answer is the empirical answer: it seems to work well in practice.  In other words, we often find in nature that very simple processes/models suffice to explain a wide range of natural observations.  See, e.g., the unreasonable effectiveness of mathematics.

There's lots more that one can say about Occam's razor.  See, e.g., https://en.wikipedia.org/wiki/Occam%27s_razor#Justifications and https://philosophy.stackexchange.com/questions/tagged/occams-razor?sort=votes.  I think that gets beyond the scope of this site.


How to analyze the Steiner tree problem? I have a problem where I am supposed to analyze the Steiner tree problem by doing the following 3 steps.

1) Look up what the Steiner tree problem is.

2) Find a polynomial time reduction to it from one of these 8 known NP-complete problems:

3-col
subset-sum
clique
hampath
Uhampath
sat
3-sat
vertex-cover.

3) Prove that it is NP-complete.

My first problem is that I don't understand what the Steiner tree problem is. I can't find the problem anywhere. Wikipedia has  a page on it, but doesn't really describe it in simple terms.

Can anyone help me out on this, and also give me hints for number 1, 2 and 3?

Short answer:  You are given a graph with some special vertices, and are asked to connected them using as few (or cheap) edges as possible.  By connecting them, we mean that you will use only those edges.

More formally, you are given a graph $G = (V,E)$ and a set $S \subseteq V$ of vertices.  These vertices are often refered to as terminals.  You are also given some number $k \in \mathbb{N}$.

I ask you now:  Can you find a set of edges $F \subseteq E$ such that (a) $|F| \leq k$ and (b) in the graph $G' = (V, F)$, $S$ belongs to the same connected component.

Now, if such a set $F$ exists and you take a subset minimal $F'$, the graph $G' = (V,F')$ is a forest, and the component containing $S$ is called a Steiner tree.

This is the unweighted decision version.  It is not hard to come up with the optimization or weighted version.  The weights are on the edges.

Edit:  When it comes to your next question, I would go for Vertex Cover.  Hint: Subdivide every edge and make the new vertices the terminals.  Then the number of edges in a Steiner tree is some function of the $E$ and the number of vertices in the vertex cover in the original graph.

And to show that the problem is in NP should be quite easy.


Approaches to the size constrained weighted set cover problem I am trying to solve a weighted set cover problem where the number of selected subsets is limited by a constant $k$.
Assuming this is a pretty straight-forward variation of weighted set cover I ended up quite confused with only one, also rather recent paper by Golab et al. [1].

Am I missing something here?

[1] Golab, Korn, Li, Saha and Srivastava, Size-constrained weighted set cover. In _Proceedings of 31st International Conference on Data Engineering (ICDE), pp. 879–890. IEEE, 2015. IEEE Digital Library; author PDF.

The problem is in P and can be solved in $O(m^k)$ time, where $m$ is the number of sets to select from.  For this reason, it is fundamentally different from standard set cover (which is NP-hard) and might not have been studied as much in the complexity theory literature.


Some points about type checking of simply typed $\lambda$-calculus? type checking

I was preparing examples of type checking in simply typed $\lambda$-calculus. I wanted to explain it to my audience in the way of implementation. And I found a bit tricky point in the typing rule of application, which is as follows.

$$
   \frac  {\Gamma \vdash t_1:T_{11}\rightarrow T_{12} \quad \Gamma \vdash t_2:T_{11}}
   {\Gamma \vdash t_1 \, t_2 :T_{12} }
 $$

$$
   \frac  {\Gamma, x:T_1 \vdash t_2 :T_2}
   {\Gamma \vdash \lambda x:T_1.t_2 : T_1 \rightarrow T_2}
 $$

Typing rules for booleans are:

$$
   \frac  {}
   {\Gamma \vdash \texttt{true}: bool }
 $$

$$
   \frac  {}
   {\Gamma \vdash \texttt{false}: bool }
 $$

My question

As far as I know, we do not need unification for type checking in the typed $\lambda$-calculus, we need unification in type inference. However, the following type checking example seems that we need something like unification, also it seems that type checking is leading to type construction.

$$
   \frac  { \vdash \lambda x:bool.x: T \rightarrow bool  \quad \vdash \text{true}: T}
   { \vdash (\lambda x:bool.x) \text{ true}: bool }
 $$
Here, $T$ is unknown type variable. It is easy to saying that $T$ is $bool$ because of the boolean typing rules, so we can continue the left branch of the above type checking as follows.

$$
\frac {x:bool \vdash x:bool}
{ \vdash \lambda x:bool.x: bool \rightarrow bool }
$$

The premise is true, so the type checking is successful.

But how do we know the value of $T$ in an implementation?
It should take matching $ true:bool$ to $true: \text{T}$ to know $T$ is $bool$. But this seems unification to me.

Also, finding $T$ for $\Gamma \vdash t: T$ is a type inference problem. So, the above type checking is leading to type inference. Am I correct?

Does type checking of the simply typed $\lambda$-calculus need unification?

Does type inference appear when doing type checking?

Please correct me if I am wrong at any point and explain.

Other info

Type checking of ${ \vdash (\lambda x:bool.x) \text{ true}: bool }$ is given as an example in the book "types and programming languages", page 103. However, it did not specify how $T$ is obtained.
Its derivation concluded $T$ is $bool$ when using the typing rule of application, as shown below.

$$
   \frac  { \vdash \lambda x:bool.x: bool \rightarrow bool  \quad \vdash \text{true}: bool}
   { \vdash (\lambda x:bool.x) \text{ true}: bool }
 $$

I believe these details are ignored in the book.

Your example is poorly chosen. In $(\lambda x : \mathsf{bool} . x) \, \mathsf{true}$ you can obviously read off the type from the $\lambda$-abstraction because it tells you that $x$ should have type $\mathsf{bool}$. A more relevant example is
$$
((\lambda f : \mathsf{bool} \to \mathsf{bool} . f) (\lambda x : \mathsf{bool} . x)) \, \mathsf{true} : \mathsf{bool}
$$
Now we are faced with determining $T$ by looking at $(\lambda f : \mathsf{bool} \to \mathsf{bool} . f) (\lambda x : \mathsf{bool} . x)$.

The usual algorithm to be used for this sort of thing is bidirectional typechecking: some terms have their types checked but others have their types inferred. No unification is required, because all types are inferred immediately. (Unification happens when we postpone decisions until a later time.)


Why k- Vertex Cover is not in PTIME when it can be expressed in FO-logic We can express property that graph has vertex cover of size at most k with first order formula:

$$\exists x_1 \exists x_2...\exists x_k (\forall y \forall z (E(z,y) \ \rightarrow \ \bigvee_{1 \leq i \leq k} y=x_i \ \vee \ \bigvee_{1 \leq i \leq k} z=x_i))$$

But, there is also theorem (proven for example in Libkin's book Finite model theory) that for every given FO sentence and finite model A one can decide does:

$$A \models \varphi$$

in PTIME.

Why can't we use this for sentence expressing k-VC property, written above, and decide does any given graph has this property?

Your argument shows that for each fixed $k$, the problem $k$-VC can be solved in polynomial time (indeed, the algorithm enumerates all sets of size $k$ and checks whether they are vertex covers, all of which can be accomplished in $O(n^{k+1})$ or so). However, the vertex cover problem is different – it accepts $k$ as an input. This version of the vertex cover problem cannot be expressed in first-order logic.


Complexity of sorting $A+A$ Is there a proof for the lower bound of the problem to create a sorted list of sums for a given list of integers with length n.

In this [thread][1] people discuss solving this problem by sorting the list of integers first and then creating the sums. However none of the solutions seems to be faster than $O(n^2 \log n)$, which is the runtime of just creating all sums and then sorting them.

How would you proof that this is the best you can get or is there a better algorithm to solve the problem.

This answer assumes that your question is about computing the sorted order of $\{ x_i + x_j : 1 \leq i,j \leq n \}$ given a list $x_1,\ldots,x_n$.

This problem is a special case of $X+Y$ sorting. According to Wikipedia, no algorithm whose complexity is better than $O(n^2\log n)$ is known for this problem. The decision tree complexity, however, is only $O(n^2)$. (That is, there is an algorithm which asks at most $O(n^2)$ decisions and outputs the sorted $X+Y$; deciding which question to ask could be difficult.)

Your version (with $X=Y$) is no easier than the general case. Indeed, suppose that $X,Y$ are integer arrays. Let $Z = \{ 4x+1 : x \in X \} \cup \{ 4y+2 : y \in Y \}$. Given the sorted version of $Z+Z$, it is easy to extract $X+Y$ by taking all elements of the form $4m+3$ and extracting $m$.

The $X+Y$ problem is 3SUM-hard. However, this doesn't shed much light on the problem since 3SUM itself can be solved in $O(n^2)$ (and even faster), while the $X+Y$ problem plainly requires $\Omega(n^2)$.


Can quantum computing help solve NP-Complete problems? i was just wondering if quantum computing has done any good so far in solving NP complete problems.
I am aware that quantum computing does solve some NP problems which are classically hard in polynomial time but as far as i know none of those problems are NP complete.
So there are a few interesting questions one could ask here:

Is there any proof or indication that such an algorithm is impossible/possible?

In this post (Why did Google not use an NP problem for their quantum supremacy experiment?) the top answer states:

However, quantum computers are not expected to be able to solve NP-complete problems significantly more "easily" than regular computers.

But it'd be nice to hear some reasoning why that is believed to be the case when other exponential time problems have already been reduced to polynomial time.

If such an algorithm were to be found for any NP-Complete problem would that mean that any NP problem could be solved efficiently by quantum computers just like classically finding a polynomial solution to an NP hard problem would prove P = NP?

BQP (the quantum analog of BPP) is closed under polynomial time reductions, so if some NP-complete problem is in BQP, then all NP-complete problems are in BQP. For more arguments, check this Quora question or that Quora question.


Algorithm Design Manual Question In the book, Algorithm Design Manual by Steven S. Skiena, he states "Becoming familiar with many different algorithmic graph problems is more important than understanding the details of particular graph algorithms." Unfortunately, I don't quite understand this phrase, as this is my first experience with Algorithm Designs. Can anyone explain the difference between the two above statements and use a real-world example where this would be true?

The author suggests that you become aware of the kinds of problems that graph algorithms can solve, rather than on the details of these algorithms. To give an example from a different field, it is much more useful to know that linear programs can be solved than to understand how the simplex algorithm works. Another example closer to the subject matter is maximum flow – again, it is more important to be familiar with the problem than with any algorithm for solving it.

You can always look up the algorithm that solves a particular problem – and if you're lucky, perhaps somebody already implemented it in some library. But you have first to know which known problems to reduce your own problem to.


Minimum number of nucleotides to force duplicate substring There are 4 DNA nucleotides, each represented by one of the letters A, C, G, or T.

Assume that they can be arranged in a string e.g. "GATTACA...". I want to figure out the minimum number of nucleotides I would have to encounter before I'm pigeonholed into seeing a duplicate substring of length 3.

Observe that a string of 4 nucleotides could produce a duplicate substring of length 3 (although I'm not forced into a pigeonhole since there are other strings of length 4 that don't produce a duplicate).

AAAA

Substrings [0-3) and [1-4) are both "AAA", so a duplicate occurrence of a length 3 substring has appeared.

I originally tried concatenating together every combination of 3 nucleotides.

[AAA][CAA][GAA][TAA][ACA][CCA]
AAACAAGAATAAACACCA...

But this algorithm produces a duplicate rather quickly: substrings [0-3) and [10-13).

I know there are 4^3 = 64 different substrings of length 3, so an upper bound to force pigeonholing is a string of length (64 * 3) + 1 = 195 -> one of the 64 substrings must appear twice. I've convinced myself that this can be bounded tighter to length 67 since this could contain 64 different substrings that start at indexes 0-63 and one duplicate that starts at 64. The interleaving of the substrings with each other is what makes them hard to analyze. How much tighter can this bound go, and what is an algorithm for producing a sequence that forces a pigeonhole?

The answer is 66: any sequence of length greater than 66 must contain some repeated substring (as you argue in the question), and there exists a sequence of length 66 where no substring is  repeated.

The latter can be obtained from a de Bruijn sequence with $n=3$ and $k=4$.  The length of this sequence is $k^n=64$  symbols.  A de Bruijn sequence is a cyclic string such that every possible length-$n$ string occurs exactly once as a substring of it.  It is known that a de Bruijn sequence of length $k^n$ exists.  If we take the de Bruijn sequence $x_1 x_2 \cdots x_{64}$, then $x_1 x_2 \cdots x_{64} x_1 x_2$ is an ordinary string where every possible length-3 string occurs exactly once as a substring.  In particular, no length-3 substring of $x_1 x_2 \cdots x_{64} x_1 x_2$ is repeated.  There are also standard algorithms to find such a string.


Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete I tried to solve the above NP-completeness exercise by making a bipartite graph from a general one (undirected) by inserting a vertice in the middle of every edge of the first (general) graph. This generates problems as suggested here: Finding the flaw in a reduction from Hamiltonian cycle to Hamiltonian cycle on bipartitie graphs
Anyone can give a hint on how to make a bipartite graph from a general one without using the above method and how the hamiltonian property can be passed to it?

Given $G = (V,E)$, define $\tilde{G} = (\tilde{V},\tilde{E})$ by adding vertices $i^+$ and $i^-$ to $\tilde{V}$ for each $i\in V$ and edges $i^-j^+$ and $i^+j^-$ for each edge $ij\in E$.

It's not too hard to check that if $|V|$ is odd, $G$ has a Hamiltonian cycle if and only if $\tilde{G}$ is.  If $|V|$ is even, just add one new vertex of degree 2 with neighbors that have an edge between them.

So far, we've seen that Hamiltonian Cycle in bipartite graphs is hard.  To reduce this to Hamiltonian Path, just continue in the way you normally would to reduce Hamiltonian Cycle to Hamiltonian Path.


Greedy algorithm for a variation of the $k$-center problem This is a variation of the well-known $k$-center problem with priorities given on the vertices.

Problem:
Let $G = (V,E)$ be a complete graph with a distances on the edges satisfying the triangle inequality. Then, additionally, there is a priority function $p: V\to (0,\infty)$. Given some $k\in\mathbb{N}$ then we wish to solve the following optimization problem
$$\min_{\substack{C \subseteq V \\ |C|\leq k}} \text{cost}(C)$$
where the cost is given by
$$\text{cost}(C) = \max_{v\in V}p(v)\cdot d(v,C) $$
and $d(v,C)$ is the distance from $v$ to its closest center $c\in C$.

Assume that we know the optimal radius $r^*$. Then we propose the following greedy algoritm:

Initialize $S = V$ and $C = \emptyset$.
Now repeat steps $3$-$5$ as long as $S \neq \emptyset$:
Select the vertex $c\in S$ with the highest priority $p(c)$.
Add $c$ to $C$, i.e. $C := C \cup \{c\}$.
Remove all vertices $v$ from $S$ that satisfies $p(v)\cdot d(v,c) \leq 2r^*$
Return $C$.

I wish to prove that this is a $2$-approximation algorithm. I'm having trouble specifically to get the $2$-factor. I've looked at some proofs of the usual $k$-center problem algorithms for inspiration, but the priority part is throwing me off.
Can anyone give a proof of the $2$-factor, or perhaps some hints?

As a hint, let me work out the case $k = 1$ for you. We are given that some set $C$ of size 1 satisfies $p(v) d(v,C) \leq r^*$ for all $v \in V$. Let $C = \{x\}$. Then $p(v) d(v,x) \leq r^*$ for all $v \in V$.

The given algorithm picks the point $c$ which maximizes $p(c)$, and then removes from $S$ all points in $A = \{ v \in V : p(v) d(v,c) \leq 2r^* \}$. We will show that $A = V$, and so the algorithm terminates after one step, outputting the set $C = \{c\}$. By construction, $p(v)d(v,c) \leq 2r^*$ for all $v \in V$, so this is a 2-approximation.

It remains to show that $A = V$, that is, that all vertices $v \in V$ satisfy $p(v) d(v,c) \leq 2r^*$. Indeed, since $p(v) d(v,x), p(c) d(c,x) \leq r^*$, the triangle inequality implies that
$$ p(v) d(v,c) \leq p(v) d(v,x) + p(v) d(c,x) \leq p(v) d(v,x) + p(c) d(c,x) \leq 2r^*, $$
using the obvious $p(v) \leq p(c)$.

All that remains is to generalize this proof for larger $k$.


What are the #P-hard version of Latin square and sudoku? I know that filling partial latin square and solving sudoku are NP-hard. But what are the counting versions of these two problems?

The counting problems corresponding to your two decision problems are:

Given a partially filled Latin square, in how many ways can it be completed to a Latin square?
Given a partially filled Sudoku puzzle, in how many ways can it be completed to a Sudoku solution?


How do I test if a polygon is monotone with respect to an arbitrary line? Definition: A polygon $P$ in the plane is called monotone with respect to a straight line $L$, if every line orthogonal to $L$ intersects $P$ at most twice.

Given a polygon $P$, is it possible to determine if there exists any line $L$ such that the polygon $P$ is monotone with respect to $L$? If yes, how?

Previously, I asked a related question (where I asked how to determine if a polygon is monotone with respect to a particular line), but now I am interested in the case when $L$ is not given or specified in advance.

It is possible.

Consider you polygon and consider the "concave" vertices. They define exactly which lines will intersect the polygon more than twice. In the following figure I marked the intervals (in red) of forbidden angles. If you put them together and see a hole in the red disk, then there are authorized angles $δ$ (in blue). The polygon is then monotonous with respect to any line of slope $-1/\tan δ$ (in green).

Now the algorithm.

Let $v_i=(x_i, y_i)$ be the $i$th vertex of the polygon. First compute the absolute angle $α_i$ of the edge $(v_iv_{i+1})$ and the inner angle $β_i$ of the vertex $v_i$. Use the function atan2 available in all good programming languages.

$$α_i=\mbox{atan2}(y_{i+1}-y_i,x_{i+1}-x_i)$$
$$β_i = α_{i+1}-α_i+
  \left\{
  \begin{array}{ll}
  0 & \mbox{ if } α_{i+1} ≥ α_i \\
  2π & \mbox{ if } α_{i+1} < α_i \\
  \end{array}
  \right.
$$

Reverse the order of the vertices if they are not in the counterclockwise order, i.e. if $s=\sum_i β_i-nπ$ is not negative. ($s=-2π$: counterclockwise, $s=2π$: clockwise).

The following is only for the $m$ inner angles bigger than $π$ that is, $β_j>π$. The red ones in my pic. The goal is to find an angle $δ$ that is not in $∪_j[α_{j+1},α_j]$ modulo $π$. Namely such that for all $j$ such that $β_j>π$:

$$(δ<α_{j+1} ∨ α_j<δ) \mbox{ if } α_{j+1}<α_j$$
$$(α_j<δ<α_{j+1}) \mbox{ if } α_j<α_{j+1}$$

where $α_j$ is here the normalized value of $α_j$ in $[0,π)$. The second case correspond to an interval that goes beyond $π$ (so this time $δ$ must be "inside").

There is probably a faster way to do this but one in $O(n^2)$ is to sort the values $α_j\mbox{ mod }π $ into $γ_1,…γ_m$ and to test for $δ∈\{\frac{γ_1}2,\frac{γ_1+γ_2}2,…,\frac{γ_{m-1}+γ_m}2,\frac{γ_m+π}2\}$.

If you have find some $δ$ then $L$ exists and is of slope $-1/\tan δ$. Otherwise $P$ is not monotonous.


What if $NP\subseteq BPP$? I'm new to complexity and came upon the following exercise which I'm unable to solve.

Prove that if $NP\subseteq BPP$ then $\Sigma_2^p=\Pi_4 ^p$.

Use the Sipser-Lautemann theorem: $\mathrm{BPP} \subseteq \Sigma_2^p \cap \Pi_2^p$.


Remove Edge From Adjacency List INPUT: weighted undirected graph in the form of adjacency list

OUTPUT: adjacency list without the edge e

Naive approach is:

for(int i = 0; i < adj.get(e.s).size(); i++) { // loop through adjacent of s
  if(adj.get(e.s).get(i).v == e.t) {           // find t and remove it
    adj.get(e.s).remove(i);
    break;
  }
}
for(int i = 0; i < adj.get(e.t).size(); i++) { // loop through adjacent of t
  if(adj.get(e.t).get(i).v == e.s) {           // find s and remove it
    adj.get(e.t).remove(i);
    break;
  }
}
O(k) - k is number of adjacent vertices

A faster approach is to use adjacencyMatrix but my algorithm has alot of traversals involved and looping through each dimension in the adjMat costs more despite a O(1) edge removal.

How can I speed up removing an edge? (used in generating a MST (kruskal))

I didn't realize what is your problem with Kruskal algorithm. To me, a usual Kruskal has time complexity $O(E \ log E)$ that $E$ is the number of edges in a graph, and I don't have any difficulty to ignore those edges which make a cycle.

To answer you question, all adjacency lists, maintaining adjacent vertices, can be sorted in an ascending order. Then, you can find the position of each adjacent node with $O(log N)$, where $N$ is the number of vertices.

You should also define two one-dimensional arrays, $nex$ and $pre$ for each adjacency list, where $nex$ maintains the position of next vertex in an adjacency list, and $pre$ holds the previous position.

When edge $e = (a, b)$ is about to be removed, the position of $b$ in the adjacency list of $a$ can be found with $O (log  \ N)$.

Then, do two following steps to remove $a \to b$:

$nex [ \ pre [b] \ ] = nex [b]$
$pre [ \ nex [b] \ ] = pre [b]$

Do it also in the adjacency list of $b$ to remove $b \to a$.

If you want to traverse in an adjacency list, the next index can be reached by the means of $nex$ array.

To traverse an adjacency list from the beginning a random value, as a dump, can be utilized since the first node might be removed.


Why RAID 2 would ever be used instead of RAID 3? According to this source and Tanenbaum's Modern Operating Systems a possible implementation of RAID 2 consists of 4 data disks and 3 disks which contain parity bits. Why don't we need 4 disks that stores parity bits, why just 3?

Also in RAID 3 we need just one disk for storing parity bytes for 4 data disks. What would be any potential interest in RAID 2 over RAID 3? As far as I understand read/write speeds are the same in RAID 2/RAID 3.

RAID 2 doesn't use parity: it uses a Hamming code. This allows error correction as well as error detection. Remember that a parity bit is just a bit that tells you whether the sum of the other bits is odd or even. It wouldn't make sense to have more than one of those because they'd all be telling you the same thing.

If you're using RAID 3 with four data bits and one parity bit, all you can do is detect when an odd number of bits have changed. You read the four data bits, add them together (mod 2) and, if the answer isn't equal to the parity bit, then you know that something has been corrupted. But you don't know what has been corrupted: it could be any one of the data bits, or it could even be the stored parity bit. All the disc controller can say is, "Sorry, but something's gone wrong and I can't give you the data you wanted."
Note that, if two bits get corrupted, you won't notice since, e.g., 1+0+0+1=0+0+1+1.

In contrast, RAID 2 would store three error-correcting bits along with the four bits of data. Having the extra two bits gives you more power: you can now detect and fix any single-bit corruption. This works by looking simultaneously at all seven bits (four data, three EC). Because of the way the code is designed, any two valid combinations must differ by at least three bits. If you see a valid combination, you're happy. If you see an invalid combination that's only one bit different from a valid one, then it must be at least two bits different from every other valid combination, so you can fix the error on the assumption that it's more likely that one bit was corrupted than two. (See Wikipedia for full details).  We assume that three bits being corrupted simultaneously is so unlikely that it will never happen: in principle, that could corrupt one valid combination into a different one.

The above assumed that two-bit corruptions are much less likely than one-bit corruptions. An alternative RAID 2 set up when two-bit corruptions aren't so rare would be to say "I don't know if this invalid combination was a one-bit or two-bit error but something's gone wrong." That would allow you to detect all one-bit and two-bit errors, but not correct anything.


Is $nHALT$ undecidable even if $M$ halts on input $w$ in finite steps If we have the language

$nHALT=\{<M,w,n>;$ $M$ halts on input $w$ in less than $n$ steps$\}$

Is this language also undecidable in the same way that $HALT$ is undecidable? And if so, $nHALT\notin P$, right?

This language is obviously decideable, just emulate $M$ on $w$ and see whether it halted within $n$ steps or not...

Now, to whether $nHALT\in P$ or $nHALT\notin P$. The length of $n$ here is logarithmic to its "value" (assuming that $\Sigma$ here is not unary). Thus, the number of steps we will need to emulate would be exponential in its size! I dont see a polynomial time algorithm for that, so I assume it's probably not in P. But I have not proven that (just gave intuition on why it could be the case), and there is also a chance that showing that is equivalent to some open problem (maybe somehow you could prove its $\mathcal {NP-Complete}$?)


Binary Search Tree – Number of comparisons when element is not found I am confused regarding Binary Search Trees (BST) when an element does not exist in the tree.

For example, to search for element "6", would it take 5 comparisons to search for this element?

My understanding is:

Compare root (Not found - move left)
Compare left node (Not found - move left)
Compare left node (Not found - move right)
Compare right node (Not found, move right)
No right node (6 does not exist)

Is my understanding correct? Would it take 5 comparisons to attempt to search for 6 in this BST?

There are only 4 comparisons: the element 6 is compared to the elements 9,7,4,5.


Incentive for block creation in a private blockchain Bitcoin miners are incentivized to produce valid blocks via a trasactional reward. But let's say I wanted to implement blockchain as part of my private data system. Who would my miner's be? I think could just have one automated miner (on a dedicated machine) with the proof-of-work difficulty being set to something very easy. But then I'm wondering, what's the point? Is there anything to gain by using a blockchain like this?

In other words, can someone please give an example---no matter how crude---of how someone could use a private blockchain to log transactions, or whether such a thing has any practical benefit to the users?

The blockchain would no longer be completely decentralized.  You would have a dictator, or a central authority that decides which transactions get processed and which do not.

At this point you could just as well skip the blockchain part of the transaction system as well.


Regarding Turing Machine Halting Problem All problems solved by standard today's general purpose computer can be solved by standard Turing machine.As general purpose computer can't do more than Turing machine so The Turing machine halting problem must also be  unsolved by today's general purpose computer.How can I realize the fact that halting problem can't be solved by todays general purpose computers.

The halting problem is the question of whether a program $B$ halts on and some given input $x$. It is impossible to create a program that decides the halting problem, so the effect is that, whatever program $A$ you create, there will exist some program $B$ and input $x$ such that $A$ will not tell correctly whether $B$ halts on input $x$.


Sensitivity versus degree Given boolean function $f$, let $F$ denote the unique multiaffine real polynomial representing $f$.

Sensitivity of $f$ at input $x$ is $$S_x(f) = |\{i:f(x)\neq f(x^i)\}|$$ where $x^i=x\oplus\Bbb 1_i$ where $\oplus$ is $XOR$ operation.

Sensitivity of $f$ is $$S(f)=\max_xS_x(f)$$

Is there an easy proof to show $S(f)\leq \mathsf{deg}(F)$?

There is a function with degree $3^n$ and maximum sensitivity $6^n$, known as Kushilevitz's function. See page 14 of this survey.

We do know that average sensitivity is bounded by the degree. This is because average sensitivity is the same as total influence, and an easy computation shows that total influence is at most the degree.


Why is a program with only atomics in SC-DRF but not in HRF-direct? In the paper "Heterogeneous-Race-Free Memory Models" [1], the authors state that a program consisting only of atomic is race free in SC-DRF but it is not in HRF-direct. I am not able to understand why this is. Can anyone explain how this can happen?

[1] Derek R. Hower et al., "Heterogeneous-Race-Free Memory Models". In Proceedings of ASPLOS '14, ACM, 2014. (PDF)

Hopefully they didn't say explicitly say exactly "a program consisting only of atomics is race free in SC-DRF."  That's incorrect.

They do say that "[in] scoped synchronization ... it is possible to write a racey program that is composed entirely of atomics if those atomics do not use scopes correctly," [top of page 2], which is slightly different (and uses the word "racey" ambiguously, perhaps leading you to believe they meant the incorrect statement.)  They perhaps should have instead said said that in scoped synchronization it is possible to write a non sequentially consistent program that is composed entirely of atomics if those atomics do not use scopes correctly.

SC-DRF (roughly: the memory semantics for C++ and Java) divide memory locations into two classes, synchronization objects, (sometimes called atomics), and data objects.  For the most part  all operations on synchronization objects are guaranteed to be sequentially consistent.[1]  (Not race free.)  This is a constraint on the compiler, not the programmer.  It says that if the programmer says that one thread writes atomic object a then writes atomic object b, all the threads will see the writes occur in this order.  (The compiler is not allowed to reorder the accesses, and is required to insert the appropriate memory barriers and fences on machines that aren't sequentially consistent.)

Sequentially consistent means that all threads on all processors agree on a total order of all memory operations.  If one thread thinks that operation $x$ happened before operation $y$, all the threads think that operation $x$ happened before operation $y$.
Sequentially consistent does not mean not racey and it does not mean deterministic.  For example, two different threads could try to write the same synchronization variable at approximately the same time.  These accesses will be racey.  A sequentially consistent system will just guarantee that if one thread thinks that write $x$ happened before write $y$, all the threads will agree that write $x$ happened before write $y$.  Sequential consistency is useful because you can use it to construct and reason about useful non-deterministic synchronization objects like mutexes and condition variables.

SC-DRF then says that if your program is data race free, the operations on data objects will appear to be sequentially consistent.  The compiler is permitted to reorder (or even sometimes eliminate) operations on data objects, and if the underlying machine is not sequentially consistent, the compiler is not required to insert memory barriers or fences.  But the compiler is not allowed to reorder operations on data objects with respect to operations on synchronization objects.

Data race free is not the same as race free.  And sequentially consistent is not the same as race free.  A particular program execution schedule is data race free if for any pair of data object accesses, $x$ and $y$, by two different threads (at least one of which is a write operation) we can use the (sequentially consistent) order of atomic object accesses to prove that either $x$ happened before $y$ or $y$ happened before $x$.  If we can not do the proof then that execution schedule is data racey.

A program is data race free if all possible execution schedules are data race free.  A program is data racey if there is an execution schedule that is data racey.

Being data race free is a constraint on the programmer, not the compiler.  It says that if your program is data racey, then your program has no semantics.  The compiler is allowed to do anything it wants, including halting the program, going into an infinite loop, or blowing up the computer.

Oh dear.  TL; DR!  I haven't even mentioned SC-for-HRC yet!

In SC-for-HRC the atomics need to specify what scope they belong to.  Atomic accesses are guaranteed (by the compiler) to be sequentially consistent only within their own scope.  All threads within the scope will agree about the order in which the atomic accesses occur, but threads in a different scope may not agree (and may not even be able to see the accesses at all, let alone their order.)

For example it might be the case that all the GPU threads agree that thread 19 acquired mutex A then acquired mutex B, but all the CPU threads do not agree (or know) that thread 19 acquired mutex A or mutex B at all.  SC-DRF does not have "scopes" so doesn't suffer this problem.

[1] The exceptions to the sequentially consistent atomics have to do with explicitly using std::memory_order_relaxed.  So don't do that.  (And I'll ignore the exceptions in the rest of what I'm saying.)


Generating cyclical dependency graphs from k-way partitions of DAGs representing boolean networks My question stems from something mentioned in the following paper*:

Acyclic Multi-Way Partitioning of Boolean Networks by Jason Cong, Zheng Li, and Rajive Bagrodia

Given a DAG representing a Boolean network, $N$, where each node represents a logic gate, define a k-way partitioning solution as $S = (A_1, A_2, ..., A_k)$ satisfying $$A_i \cap A_j = \emptyset \quad{\text{and,}}$$ $$\bigcup\limits_{i=1}^{k} A_i = N$$

Then define a dependency graph $D(S)$. This is a directed graph with $k$ nodes where each node represents a block, $A_i$, and has an edge $(A_i,A_j)$ if and only if there exists an edge $(x,y)$ in $N$ such that $x \in{A_i}$ and $y \in A_j$ (in other words, the edges are the edges removed when forming the partition).

The authors note that it is possible to get dependency graphs that are cyclic after some k-way partition. My question is, how is this possible? I can't seem to come up with an example where partitioning a DAG would ever produce a cyclic dependency graph. As I see it, a cyclic dependency graph would require a an edge to be "reversed" somehow, which would produce a cycle in the original DAG. Perhaps it has something to do with the fact these graphs are representing boolean networks?

*Link to pdf may be paywalled

**Note the authors also have a balance constraint on the partitions which I didn't describe but I don't think that's relevant to my question.

Consider the following graph on three vertices:

$$u \to v \to w$$

This is acyclic.  If you set $A_1 = \{u,w\}$ and $A_2 = \{v\}$, you end up with a dependency graph that is cyclic: it has an edge $A_1 \to A_2$ (due to the edge $u \to v$) and an edge $A_2 \to A_1$ (due to the edge $v \to w$).


Is the class NP closed under complement? Is the class $\sf NP$ closed under complement or is it unknown? I have looked online, but I couldn't find anything.

First of all, the question you are asking is open, since an affirmative answer shows that $\sf NP = coNP$. In fact it is one of the most prominent open problems in computer science.

If $\sf P= NP$, then the class $\sf NP$ is closed under complement since $\sf P$ is. If on the other hand $\sf P \not = NP$ then we cannot say whether $\sf NP = coNP$ or not. Notice that $\sf NP = coNP$ implies that the polynomial hierarchy collapses to the first level. However this would not imply that $\sf P= NP$.


Can this set of propositions be represented and proved in Haskell? I used a set of natural language statements and their formalization  from  Gries and Schneider. I attempted to transform the propositions into Haskell equations. For example, for S0 : $a \land w \Rightarrow p$ the conjunction was split giving $a \Rightarrow p$ and  $w \Rightarrow p$ and then the contrapositive rule was applied giving  $\neg p \Rightarrow \neg a$ and  $\neg p \Rightarrow \neg w$. I then translated those propositions into Haskell conditional equations.

Is the Haskell representation a reasonable transformation?  Is there a relation between the execution of the Haskell expression not e a proof of theorem $\neg e$?

Natural language

If Superman were able and willing to prevent evil, he would do so. If Superman were unable to prevent evil, he would be ineffective; if he were unwilling to prevent evil, he would be malevolent. Superman does not prevent evil. If Superman exists, he is neither ineffective nor malevolent. Therefore Superman does not exist.

Formalize

$a$: Superman is able to prevent evil.

$w$: Superman is willing to prevent evil.

$i$: Superman is ineffective.

$m$: Superman is malevolent.

$p$: Superman prevents evil.

$e$: Superman exists.

S0 : $a \land w \Rightarrow p$

S1 : $(\neg a \Rightarrow i) \land (\neg w \Rightarrow \neg m)$

S2 : $\neg p$

S3 : $e \Rightarrow \neg i \land  \neg m$

module SUPERMAN where
 a::Bool
 w::Bool
 i::Bool
 p::Bool
 e::Bool

 a | (not p) = False  -- S0a
 w | (not p)  = False -- S0b
 i | (not a) = True   -- S1a
 m | (not w) = True   -- S1b
 p = False            -- S2
 e | (i || m) = False -- S3
-- Theorems (not e), (i || m), and (i && a) all hold

Your Haskell encoding fails to capture proofs in propositional calculus (which is what the book you referred to does). The failure is not due to your using Haskell, but because of your encoding evaluation of Boolean values instead of proofs, and these are two completely different things.

When people speak about "Haskell proving things" they mean the following: given a type t which represents a proposition $T$ via the propositions as types translation, does there exists a Haskell program p of type t which corresponds to a proof of $T$?

Example: the proposition $((A \land B \Rightarrow C) \Rightarrow (A \Rightarrow B) \Rightarrow (A \Rightarrow C)$ corresponds to the (polymorphic) type ((a,b) -> c) -> (a -> b) -> (a -> c). The program \ f g x -> f (x, g x) has this type, and therefore corresponds to a proof of the proposition. The kind of logic that can be represented in this way is intuitionistic.

However, because Haskell has general recursion, not every Haskell program corresponds to a proof, and in fact Haskell cannot be considered as a proof system. It is a programming language. A better choice is Agda or Idris.

You are translating propositions into Boolean algebra which you then encode using the Haskell datatype Bool. You are therefore misusing the phrase "prove in Haskell". At best you are trying to evaluate Boolean expressions, which is not the same thing. You defined, in a somewhat convoluted way, a (partial) evaluation strategy that evaluates various Boolean propositions. It's not a very good one, for instance if you change p = True line to p = False, your program fails to evaluate a.

This has nothing whatsoever to do with Haskell because it is not specific to it. You can do the exact same thing in just about any programming language, and even in Excel. However, as was suggested already twice, prolog seems to be the most appropriate tool for the problem at hand. You are not "researching" Haskell here. I believe we already tried to explain this to you in the previous question you linked to. I hope it gets across this time.


Is it possible to solve the Mountain Car reinforcement learning task with linear Q-Learning using the state as direct input? I'm trying to solve the Mountain Car task on OpenAI Gym (reach the top in 110 steps or less, having a maximum of 200 steps per episode) using linear Q-learning (the algorithm in figure 11.16, except using maxQ at s' instead of the actual a', as required by Q-learning; I've solved it with other methods easily, the question is about linear Q-learning). Also, I'm using 1 output for each action, so I can select an action in a single forward pass. Important: my input features are the identity function of the state, i.e., the state variables themselves. I know it can be solved with other features, I want to know about this one specifically.

Here is a description of the algorithm I'm using: https://youtu.be/vVDKzIxzkzQ

Unfortunately, this method never solves the task. Actually, it rarely reaches the top. I'm aware that vanilla Q-learning has no convergence guarantees, so I tried some variants which reduce or even solve this issue: I've tried experience replay, double q-learning, GTD and advantage learning. Nothing helped.

I know that this task can be solved linearly on the state inputs directly, since I've done it by manually tuning the weights so the car always apply the force in the same direction as its velocity, so the representation is not an issue. But it seems that the learning algorithm is.

So the question is: is linear Q-learning able to learn the mountain car task directly from the state variables? A paper where the author solves this task with Q-learning in a single-layer network (and shows the algorithm or code) with features = state variables would be enough.

I just found out the answer and it's actually pretty simple: while there is a good linear policy for the mountain car task, the value function itself is non-linear.

The state space of this task is like a spiral, and there is no linear approximation possible even for a mediocre value function. If you increase the value for going right and reaching the top, going left will have the lowest values. This is why the car never reaches the top.

By applying a simple random projection and transforming the input space, it is possible to show that the task becomes linearly solvable (with a value-based method).


Finding all faces in a wireframe mesh I'm trying to find an algorithm for finding all faces in a wireframe mesh.  Wireframe means only the vertices and edges are given as input.  There is no restriction on the number of edges a resulting face can have and the face can be convex or concave.

Simple Example

In a wireframe of a square-based Pyramid there are 5 faces - the base is a square and the sides are triangles.

The algorithm should produce 5 sets of edges (since there are 5 faces).  One set of edges would contain the 4 edges that make up the square base and then 4 sets of 3 edges for each side of the pyramid.

Bonus

It would be a bonus if the algorithm can create an edge winding resulting in all faces pointing inwards or outwards.

After conducting more research I did find a solution, but first I will examine solutions suggested by posters and considered by myself and review why they didn't work.

This problem reduces to finding all chordless cycles in a planar graph.

This was one of my first thoughts early on, but this doesn't work when you consider the following:

      5-------f-------6
     /               /|
    /               / |
   e               g  |
  /               /   h
 /               /    |
1-------a-------2     7
|               |    /
|               |   /
d               b  i
|               | /
|               |/
4-------c-------3

Given three sides, the answers should be: 1 2 3 4 1, 1 5 6 2 1, and 2 6 7 3 2.  Unfortunately, 1 4 3 7 6 5 1 is considered chordless and is not a correct answer.

If you have vertices and edges - connect them. Adjacent edges will constitute a face.

Unfortunately, without weighting or accounting for spatial information you'll end up running into the edge cases described below.

Edge Cases

The highlighted "face" in the following two examples should not be in the solution.  These highlighted faces are referred to as "internal faces" (yes, even the highlighted face on the right is considered an internal face in graphics terminology).

Then there are other issues like objects with distinct subgraphs, holes, and ambiguous face loops.

The Solution

While researching I found the paper: A new algorithm for finding faces in wireframes by Peter A. C. Varley and Pedro P. Company (full text here).  The algorithm attempts to solve the problem for both 2D and 3D input.  The solution is non-trivial: the setup alone is polynomial time.

Basic Description

Start by creating a set of directed edges from all edges of the graph (so the initial set is of size 2e were e is the number of edges).  These sets of directed edges are stored as the vertices that comprise them and are referred to by the paper as "strings".  Each string must be given a priority according to the geometry around it (e.g. there will be a different priority assigned depending upon if it touches a triangle or quadrilateral).

You then exhaustively attempt to merge the strings by finding ones that start were another one ends.  You do this by picking the highest priority strings first.

When merging strings you remove the original strings from the set and add the merged version back in.  When the merge is preformed a new priority must be calculated using the existing priorities and spatial information about the strings themselves (the spatial calculation differs depending upon if your running the algorithm against 2D or 3D input).

Strings are removed from the set if their first and last vertex match (that means a loop was found).  You continue repeating the algorithm until the set is empty.

Complete Algorithm

Here is the complete algorithm copied directly from the paper.  Hopefully the description I gave above helps a bit.  The paper is very well written and its a good read for anyone interested in the topic.

Some steps in the algorithm come down to guesswork and assumptions about the input.  For example, step #3 says to "choose a trihedral vertex", but if there is no trihedral vertices (e.g. octahedron or icosahedron) then the paper suggests breaking the symmetry by assuming that an arbitrary triangular loop of edges is a face.

(Top level of algorithm)
Create initial master string list, two entries per edge
Assign priorities to all strings in the list
Choose a trihedral vertex, and concatenate two strings at this vertex
While there are strings remaining in the master list
Examine the master list for the presence of forced concatenations
    If there are forced concatenations, perform them
    Otherwise, examine the master list for the presence of voluntary mergers
    If there are voluntary mergers, perform them
    Otherwise, examine hypotheses (see subroutine below)
(Subroutine: Examine Hypotheses)
Take a working copy of the master string list
Repeat
Take the highest-priority string S in the working string list
Find the string T which has the best mating value with S
Concatenate S and T, and reduce the priority of the resulting string
Repeat
Examine the working string list for the presence of a forced concatenation
If there is a forced concatenation, perform it
    If the forced concatenation created a new face, update the master list accordingly and exit this subroutine
If there is no forced concatenation
    If there is a voluntary merger available, create the face, update the master list accordingly and exit this subroutine
    Otherwise exit this inner loop

Other Solutions

According to the paper, the current face-finding algorithms generally fall into four categories: exhaustive search approaches, pseudo-random approaches,
shortest-path approaches, and heavily mathematical approaches.  It does a good job citing other possible solutions along with their advantages and disadvantages.

Keep in mind that this algorithm acknowledges that it still produces incorrect output for certain input.  However, this is still an improvement over the previous best solution which fails for even more input.


Unclear logic notation for PFX program rules I'm very new to this so please bear with me.

I found this document describing the PFX language, a stack-oriented language where the instructions act on a stack and replace the arguments with the result.

The image is supposed to be the rules describing the logic of a PFX program, but being very new to logical symbols, I can barely read it.

From what I understand, the top parts are suppositions and the bottom parts are conclusions. The first one, to me, reads, if i is different from n, then if either of the vk's implies i, the program declares an error. But I can tell my understanding is deeply flawed. I searched and have found close to no similar rules.

Also, the use of the letter "i" seems unclear to me mostly.

If someone can explain with words what the rules actually mean, it would help me a lot.

Thank you.

The "fraction"-style notation is an inference rule in natural deduction style.  See What is this fraction-like "discrete mathematics"–style notation used for formal rules?.

$v_1,\dots,v_n\vdash \cdots$  means "in the environment $v_1,\dots,v_n$, such-and-such is true".  (It's not an "or", and it doesn't mean "implies".)  See What does ⊢ mean in operational semantics?.

I recommend finding a good textbook on programming language semantics, and reading it.  It will give you some background that will help you understand that notation.  It's probably too much to explain all of that in a single answer here.


Determining asymptotic notation of a complex function $$
5n^4\log{n} - \frac{100n^2}{\log_4(n^2)} + 40
$$

I am currently studying algorithm analysis and i need to express this function in terms of big O, theta and omega, so I should find C, and N0 for each case I solved big Oh with c=40 and n0 = 1 but I am stuck here any help ?

If you check the definitions, big-O means "bounded from above" (with a fudging constant $c$ multiplying it all, starting at a high enough $n$), you can disregard "constants multiplying" and "slower growing terms"; so you can say:

$\begin{equation*}
 5 n^2 \log n - \dfrac{100 n^2}{\log_4 n^2} + 40
   = O(n^2 \log n)
\end{equation*}$

(could also say $O(n^3)$, or $O(n^4 \log^{10} n)$ for that matter, bound from above).

For a lower bound, the same works fine:

$\begin{equation*}
 5 n^2 \log n - \dfrac{100 n^2}{\log_4 n^2} + 40
   = \Omega(n^2 \log n)
\end{equation*}$

For a lower bound, $\Omega(1)$ or $\Omega(n \log n)$ work fine too.

As you have the same upper/lower bound:

$\begin{equation*}
 5 n^2 \log n - \dfrac{100 n^2}{\log_4 n^2} + 40
   = \Theta(n^2 \log n)
\end{equation*}$

Finding values of $c$ and $N_0$ I leave to you. They can be different for $O$ and $\Omega$!


Prove that ${NP}^{NP}=\Sigma_2$ I've head the lecture today and we saw this theorem:

$\mathsf{NP}^{\mathsf{NP}}=\Sigma_2$

But without a proof.
Here are the definitions I use:
A language $L$ belongs to $\Sigma_k$ if there is a deterministic Turing machine $M(x,y_1,y_2,\dots,y_k)$ such that:

There exists a constant $c$ such that $|y_i|=|x|^c$ and $M(x,y_1,y_2,\dots,y_k)$ runs in time $\mathit{poly}(|x|)$.
$x\in L$ iff $\exists_{y_1}\forall_{y_2}\exists_{y_3} \dots M(x,y_1,y_2,\dots,y_k)=T$,
where the quantifiers are alternating between existential and universal, and start with existential.

$\mathsf{NP}^{\mathsf{NP}}$ is the class of all languages of languages in $\mathsf{NP}$ with oracle calls to a language in $\mathsf{NP}$.
I thought maybe to use $\mathsf{SAT}$ as it is an $\mathsf{NP}$-complete language.
Can someone please help me understand why this is true?

Suppose first that $L \in \Sigma_2^P$. Then there exists a machine $T(x,y,z)$, running in time $\mathit{poly}(|x|)$, such that
$$
x \in L \Leftrightarrow \exists y \forall z \, M(x,y,z) = T
$$
Using the reduction in Cook's theorem, given $x,y$, we can express $\exists z \, M(x,y,z) = T$ as a SAT instance. Therefore given a SAT oracle, we can verify that $y$ satisfies $\forall z \, M(x,y,z)$. This shows that $L \in \mathsf{NP}^{\mathsf{NP}}$.
In the other direction, suppose that $L \in \mathsf{NP}^{\mathsf{NP}} = \mathsf{NP}^{\mathsf{SAT}}$. There is thus an oracle Turing machine $M(x,y)$, running in time $\mathit{poly}(|x|)$, such that
$$
x \in L \Leftrightarrow \exists y \, M^{\mathsf{SAT}}(x,y) = T.
$$
(The notation $M^{\mathsf{SAT}}$ means running $M$ with a SAT oracle.)
How can we tell that $M^{\mathsf{SAT}}(x,y) = T$ without access to a SAT oracle? The idea is to "guess" the answer of every SAT query, and prove the necessary information to verify this answer. Suppose that $M$ queries $q \stackrel?\in \mathsf{SAT}$. If $q \in \mathsf{SAT}$ then we can provide a witness for it, namely a satisfying assignment. If $q \notin \mathsf{SAT}$ then we know that every assignment does not satisfy $q$.
Accordingly, we construct a machine $M'(x,y',z')$ in the following way. The witness $y'$ consists of the original witness $y$, together with the following information: the number of SAT queries performed by $M$; for each SAT query $q_i$, the answer $b_i$; for each positive answer, the corresponding satisfying assignment $a_i$. The "cowitness" $z'$ consists of an assignment $a_i$ for each negative answer to a SAT query.
The machine $M'$ acts simulates $M$. Whenever $M$ makes a SAT query $q_i$, it determines the answer from $y'$. If $b_i = T$, it verifies that $a_i$ is a satisfying assignment for $q_i$. If $b_i = F$, it verifies that $a_i$ is not a satisfying assignment for $q_i$. The new machine $M'$ accepts if all verifications
succeed, and additionally $M$ accepts.
This shows that $L \in \Sigma_2$, completing the proof of your statement.


Is Differential Evolution a genetic algorithm? I am trying to classify the Differential Evolution algorithm according to the framework in the book:

  Introduction to Evolutionary Computing

The authors classify the field of evolutionary computation into 4 paradigms:

Evolutionary programming
Genetic programming
Evolutionary strategies
Genetic algorithms

I have ruled out 1. and 2., since they deal with programs as opposed to abstract optimization problems. I also ruled out 3. since evolutionary strategies maintain an explicit random distribution during the optimization process. That leaves only genetic algorithms. But when you say "genetic algorithm", the firs thing that comes to most peoples' minds is the traditional flipping of 0s and 1s. I have personally never heard anybody refer to differential evolution as a genetic algorithm.

If you're asking for a homework assignment, then I can't really help you, because the answer really depends on how your professor interprets the taxonomy. But if you're asking for your own edification, I can give you my view.

First, the distinctions between the four classes you list (particularly between 1, 3, and 4) are largely historic. There are still some very real differences of course, but we don't view the lines between them as sharply as we once did. This means, for example, that GAs can be real-valued instead of binary and might rely on mutation more than crossover. You can have an evolution strategy for the traveling salesman problem. Really the description in the book isn't terribly well suited for use as a taxonomy for this reason. I teach from this book, and I like it a lot, so that's not really a criticism. I don't think the authors intended for you to try and use it as a well-defined taxonomy either.

If we go with this idea as a rough taxonomy though, then in principle, we have an umbrella term: "Evolutionary Computation" or "Evolutionary Algorithms" that covers all four of the cases you list. In practice though, while if someone says "evolution strategy" or "genetic programming", it's because they intentionally want to highlight that that's what they're doing, people sometimes say "genetic algorithms" when they really mean "evolutionary algorithms". So that term is especially hard to interpret.

So we might be able to call DE a GA with that understanding and be OK, but it really depends on who's asking the question as to whether that's what they had in mind or not.

Looking at the problem another way though, it gets even fuzzier. Right now, you're reading someone else's taxonomy and trying to fit the pieces together. What if you take a step back and try to formally define what a genetic algorithm or evolutionary algorithm is yourself? You might come up with something like "an algorithm that maintains a population of one or more candidate solutions, usually generated randomly, and continually selects the better individuals from the population, produces new individuals from the old ones via some type of variation operators, and favors the better of these new individuals for insertion into the population".

It's hard to get much narrower than that without excluding some things we think are "obviously" evolutionary algorithms, but this definition is really very broad. Certainly things like differential evolution and particle swarm optimization meet this definition, but so does, for example, simulated annealing. You can even take a simple next-descent hill-climber and call it a (1+1)-ES.

Personally then, my answer to your question is "sort of". If I write a paper that proposes a novel DE variant that looks super-awesome, I'd absolutely submit it to a journal like Evolutionary Computation. I know that my algorithm would be viewed as being appropriate for a venue that focused on genetic and evolutionary algorithms. But I probably wouldn't tell people that I used a "genetic algorithm" either, because that term doesn't feel precise enough to capture what it is that I want to express.

I'm not sure this is a particularly helpful answer, but I think it's probably a pretty common view among people in the field.


How does the NegaScout algorithm work? On Alpha-Beta pruning, NegaScout claims that it can accelerate the process by setting [Alpha,Beta] to [Alpha,Alpha-1].

I do not understand the whole process of NegaScout.

How does it work? What is its recovery mechanism when its guessing failed?

Sorry for the late reply (4 years!)

NegaScout is a very simple algorithm. To understand we should revise iterative deepening.

Iterative deepening is a technique for a chess engine to search for depth i, then i+1, then i+2 etc. This is an example of dynamic programming. During each iteration we have our best guess of what the best move would be. Most chess engines would keep this move in a hashing table.

Imagine we are now at iteration i+1, and we have the best move from the last iteration i. Now we have 5 nodes to search, we should we do?

If we assume we have done reasonably good job during our last iteration, the best move from the last iteration (which we get from the hash table) should also be the best move for the current iteration.

If our assumption is correct, we should be able to save time by searching every move other than the best move (the four moves not in the hash table) with a null window. A null window is something like:

score := -pvs(child, depth-1, -α-1, -α, -color)

Note -α-1 and -α. They are the alpha and beta values we will give to the next recursion. Since the width of the window is only 1, the search will always fail:

If it fails below α, the move is worse than we already have, so we can ignore it
If it fails above β, the move is too good to play, so we can ignore it
Otherwise, we need to do a new search properly

Of course, we will still search the best move (the one we get from the hash table) with a proper alpha and beta window. We need to do this because we need to know exactly the value of the node, we can't just ignore it.

Everything I've said is implemented in the following pseudocode. The pseudocode specifies child is not first child but this is a way to check whether the move is also the best move int the previous iteration. Hash table is the most common implementation.

# Negasort is also termed Principal Variation Search - hence - pvs

function pvs(node, depth, α, β, color)
    if node is a terminal node or depth = 0
        return color x the heuristic value of node

    for each child of node
        if child is not the first child
            # search with a null window
            score := -pvs(child, depth - 1, -α - 1, -α, -color)

            # if it failed high, do a full re-search
            if α < score < β
                score := -pvs(child, depth - 1, -β, -score, -color)
        else
            score := -pvs(child, depth - 1, -β, -α, -color)

        α := max(α, score)

        # beta cut-off
        if α >= β
            break

    return α


Why can't DFS be used to find shortest paths in unweighted graphs? I understand that using DFS "as is" will not find a shortest path in an unweighted graph.

But why is tweaking DFS to allow it to find shortest paths in unweighted graphs such a hopeless prospect? All texts on the subject simply state that it cannot be done. I'm unconvinced (without having tried it myself).

Do you know any modifications that will allow DFS to find the shortest paths in  unweighted graphs? If not, what is it about the algorithm that makes it so difficult?

The only element of depth-first search you tweak is the order in which children are investigated. The normal version proceeds in arbitrary order, i.e. in the order the children are stored.

The only feasible alternative (towards shortest paths) I can come up with is a greedy approach, that is looking at children in order of their distance from the current node (from small to large). It is easy to construct a counterexample for this rule:

[source]

Now, that is no proof that there does not exist a strategy of choosing the next child to be investigated which will make DFS find shortest paths.

However, no matter the rule¹ you can construct graphs that have DFS commit to a long detour at the very first node, just as I did for the greedy rule. Assign edges $(s,t)$ and $(s,a)$ weights such that the rule chooses to visit $a$ first, and assign $(a,b)$ a weight greater than the one of $(s,t)$. Therefore, it is plausible that DFS can never find shortest paths (in general graphs).

Note that since you can express every (positive-integer-)weighted graph as unweighted graph -- simply replace edges with cost $c$ with a chain with $c-1$ nodes -- the same examples deal with DFS on unweighted graphs. Here, the situation is actually even more bleak: without weights, what can DFS use to determine the next child to visit?

As long as the rule is deterministic. If it is not, it can clearly not always find shortest paths.


Does P not NP imply NP COMPLETE disjoint from RP? According to Wikipedia https://en.wikipedia.org/wiki/RP_(complexity), $P \ne NP$ implies that $RP$ is a strict subset of $NP$. Does anybody have a reference?
Furthermore, am I correct that if this indeed the case, then $NP-COMPLETE \cap RP = \emptyset$ since we can use $NP$ completeness to solve all other $NP$ problems?

You have not accurately summarized the statement in Wikipedia.  The statement in Wikipedia also needs the extra assumption that $P=BPP$, which is widely conjectured but has not been proven to be true.
With that clarification, no reference is needed -- the reasoning is straightforward and already described on Wikipedia.  If $P=BPP$, then $P=RP=co-RP$ (since $BPP=co-BPP$ and $RP \subseteq BPP$ and $co-RP \subseteq BPP$).  If additionally $P \ne NP$, then it follows that $RP \ne NP$.
Yes, if $RP \ne NP$, then $NPC \cap RP = \emptyset$.