Is 2-DNF NP-complete? I want to know whether the 2-DNF problem is NP-complete or not? If it is NP-complete, can anyone provide a proof?

If you are referring to the problem of deciding whether a formula given in $2-DNF$ form is satisfiable, then it is in $P$, as well as general $DNF$ satisfiability. Indeed, such a formula is satisfiable iff there is a clause that does not contain an inner contradiction. That is, a clause that does not contain both $p$ and $\neg p$ for some atomic proposition $p$. This can be checked in linear time.

Perhaps you are referring to $2-CNF$? (which is also in $P$, but it's less trivial).


What information do we get from a compiler's parse tree? In the compiler course by Alex Aiken on Coursera, more specifically lecture 05-02 Context Free Grammars,  the professor says that CFGs give answers of the type yes/no, i.e. whether the given string of tokens is valid or not. He adds that it is also desirable to know how a particular string of tokens is in the language; for this purpose he introduces parse trees.

Why is the "how" part important?

Prelude It might be useful to be pedantic and start with a surprising fact: compilers do  not use context free grammars, contrary to what you've been told. Instead they use  something closely related but subtly different, which might be termed context-free transducers (please let me know if there's an official name for it). They relate to context free grammars as Mealy-machines do to finite state machines.

The reason why CFGs are not used is that CFGs only give a yes/no answer. That's not enough for the subsequent stages of a compiler. Instead, subsequent stages need a good representation of the input program to work with. This representation is the abstract syntax tree (AST). Something similar happens in lexical analysis: contrary to what most compiler courses tell you, the lexer does not use a finite state machine or regular expression to nail down the lexical structure of a language, because regular expressions and finite state machines also only give a yes/no answer. We want the output of the lexical stage to be a token-list for consumption by the parser. Mealy machines deliver token lists.

If this is the case, why do compiler courses usually use regular expressions and finite state machines for the lexical analysis and CFGs for parsing? Do compiler teachers lie to us? No, they want to help us understand:

The concepts are really similar, e.g. a Mealy machine is just a finite state machine where every transition carries not just an input action (as they do with finite state machines) but also a corresponding output action. Likewise context free transducers are just CFGs where every production is also associated with an output.
Teachers don't want to be overly formal, and expect the students to bridge the gap between
finite state machines and lexer / CFG and parser themselves. In practise students almost always do.

Main point. With  this pedantic caveat we can come to the original question: what is the parse tree used for?

The parse tree contains the
 "how a string is in the CFG". The parse tree is used to construct the abstract syntax tree (AST) which is a concise representation of the program that is used by later phases in the compiler, in particular the type checker (for statically typed languages) and the code generator. The advantage of ASTs over other program representations such as strings is that ASTs make access to the immediate sub-programs of a program easy, e.g. the program

if C then P else Q

has three immediate sub-programs namely C, P and Q. The AST for the program has three pointers to the sub-programs:

Both, code-generation and type-checking, involve the recursive invocation of code-generation/type-checker on the immediate sub-programs (plus some glue-code). Hence ASTs provide exactly the information needed for efficient type-checking and code generation.

The relationship between parse trees and ASTs is simple.
The parse tree contains the exact information about how a string 'fits' into the CFG. Every production applied when consuming the input string is noted down in the order used. This
information has a natural tree shape, whence the name "parse tree". An AST is a parse-tree with redundant information removed. An example of redundant information are properly balanced brackets. Another example is the node labelling that
gives the aforementioned information about what productions were used to derive the string. Such information
is important for checking if the input string (or more precisely token-list)
is syntactically valid, but once that has been acertained, this information is no longer
needed for compilation and hence discarded.

Let us look at an example. Consider the arithmetic expression $4 *(3+17)$ in the obvious grammar of arithmetic expressions:
$$
   E \ \ \rightarrow\ \ E + E \ |\ E * E \ |\ ( E ) \ |\ 0 \ |\ 1 \ |\ 2 \ |\ ...
$$
Let's ignore the ambiguity and left-recursion in that grammar. Here is a plausible parse tree for $4 *(3+17)$

(Note that the parse tree is usually not constructed explicitly, but is implicity in the structure of the recursion throughout the parsing process.)
The corresponding AST is simpler, but still contains all relevant information, including
precedence of the addition over the multiplication, in its pointer structure:

Summary: compilers construct ASTs (good representation of the program for future compiler stages) from parse trees (which tell "how" the program is in the CFG).


Example using Penetrance & Branching Factor in State-space Heuristic Search I need an example for how to calculate penetrance and branching factor of the search tree in in state-space heuristic search. The definitions are as following. Penetrance $P$ is defined by

$\qquad \displaystyle P = \frac{L}{T}$

and branching factor $B$ is defined by

$\qquad \displaystyle \frac{B}{(B-1)} \cdot (B^L – 1) = T$

where $L$ is the length of the path from the root to the solution and $T$ the total number of nodes expanded.

Consider the following search tree. Your heuristic search algorithm starts the search at the root node. Unexpanded nodes are marked gray.

For some reason, the heuristic is being guided towards the left-most subtree, when in fact the goal node is in the right-most subtree, marked with green.

Nodes that have been expanded are marked red. After the appealing left-most subtree turned out to be a dead-end, the heuristic is now luckily being guided directly towards the goal. From the situation of the previous figure, we'll expand a total of three new nodes before arriving at the goal.

From the figure above, the length of the path to the goal is $3$. There are $17$ expanded nodes. Therefore, the penetrance is $3/17 \approx 0.43$.

The branching factor is the maximum number of successors of any node. For example, the branching factor of a binary tree is $2$ since each node has at most two children. Likewise, in the above search tree the branching factor is $3$.

What you seem to be interested in is not the branching factor, but the effective branching factor $B^*$ which is a way to characterize the quality of a heuristic. If the total number of expanded nodes is $T$, and the length of the path to the goal is $L$ (this is more commonly known as depth), then $B^*$ is the branching factor that a uniform tree of depth $L$ would have in order to contain $T+1$ nodes. Therefore,

$$T+1 = 1 + B^* + (B^*)^2 + \cdots + (B^*)^L.$$

If you plug-in the values we obtained in search, that is, $T=17$ and $L=3$, you get $B^* \approx 2.165$. This is exactly the same value you get from using your equation; it's just merely a different representation for the same thing.

The effective branching factor can vary across instances, but is somewhat constant for hard enough problems. A well-designed heuristic would have a value of $B^*$ close to $1$, allowing fairly large problems to be solved reasonable cheaply.


Is a graph at least k-colorable? (Complexity) I am new to the complexity theory and I am trying to understand what would be the complexity of the following problem: "Is a graph AT LEAST $k$-colorable?"
Whether a graph is $k$-colorable is clearly a NPC problem and is explained by reduction to 3-SAT.
However, I am not sure to which complexity class belongs the modified problem I have stated. Does it belong to NP as well? My guess is that we would be able to check it with a polynomial certificate (any $\geq k$ coloring of the graph).
And then the problem "Is a graph AT MOST $k$-colorable?" would be its complement in co-NP unless NP=co-NP?

Well, all graphs are colorable with $\geq k$ colors: Assign each vertex a different color (and leave the other color classes empty if $k$ is larger than the number of vertices of the given graph).
As for the complement of this problem, note that you did not correctly invert the definition of the problem:
A problem $L$ is, after all, merely a set of strings over some finite alphabet $\Sigma$ representing some objects with some property.
Its complement is then the set $\Sigma^\ast \setminus L$ or the set of all strings not representing an object with the property.
If we recall the argument above, we find that the complement of your problem is hence the set of all strings not representing graphs (under that fixed encoding scheme) rather than the one you claimed. This problem (as the first one), is in $\mathsf P$.


Generating graph with complex structure I want to generate a bunch of graphs of about 100 nodes, where each node is a categorial variable.  I want the graphs to satisfy complex properties, like, "if a node of type A is connected to a node of type B, that node of type B should also be either connected to both a node of type C and a node of type D, or should be connected to a node of type E" and "no nodes of type F and G can be connected to the same node."  How do I go about generating such structures?  I was thinking of using an SMT solver, but even then I'm not exactly sure how to proceed.  For instance, is there a way to do it using only BitVectors?

I would use a SAT solver.  Use one boolean variable per edge to encode whether that edge is present or not.  Encode the type of a node via a one-hot encoding ($k$ variables per node, where $k$ is the number of possible types).  Then each constraint you mention should translate directly into a simple formula on a few of these boolean variables.

I like Z3 for ease of programming.

I see no reason nor benefit to using bitvectors or SMT; plain SAT should suffice.


An online algorithm to maintain the Pareto frontier elements I'm looking for an online algorithm/datastructure that is able to maintain a pareto frontier for two dimensional elements in an online scenario where elements can be added and deleted.

For example:

insert((3,7))

since the pareto front is empty it has to be added to it
set of elements E={(3,7)}
pareto frontier P={(3,7)}

insert((7,3)) and insert((10,2))

both have to be added to pareto frontier (since they arent dominated)
set of elements E={(3,7), (7,3), (10,2)}
pareto frontier P={(3,7), (7,3), (10,2)}

insert((8,4))

is dominated by (7,3) so do not add it to the pareto frontier (but keep it in the set of elements E because its maybe going to be part of the pareto frontier later)
set of elements E={(3,7), (7,3), (10,2), (8,4)}
pareto frontier P={(3,7), (7,3), (10,2)}

remove((7,3))

remove (7,3) from the set of elements and from the pareto frontier. The pareto frontier has to adjust accordingly and therefore (8,4) is added to the pareto frontier now.
set of elements E={(3,7), (10,2), (8,4)}
pareto frontier P={(3,7), (10,2), (8,4)}

This question is similiar to An online algorithm to find the Pareto frontier elements, but in the scenario described above points can also be removed. A brute force algorithm would have quadratic time complexity and I am looking for something better.

You can find an answer to this in "Dynamic Planar Range Maxima Queries", by Brodal and Tsakalidis. They support insert and remove in $O(\log n)$ time. That paper points to several previous papers that addressed the question as well.

In particular, I expect the simplest solution can be found in sections 8 and 9 of "Maintenance of Configurations in the Plane", Technical Report RUU-CS-79-9, by Overmars and van Leeuwen, (mirror). Their solution takes $O(\log^2 n)$ for each insert or remove.


Why L is defined as L = SPACE$( \log n)$ instead of L = SPACE$(\log^2 n)$ or L = SPACE$(\sqrt n)$? $L$ is the class of languages that are decideable in logarithmic space on a deterministic Turing machine. In other words,

  L = SPACE$( \log n)$

But why $\log n$, instead of $\log^2 n$ or $\sqrt n$. This is what, I find out in the Theory of computation book by Michael Sipser Theory of computation book by Michael Sipser, Chapter 8

  Logarithmic space is just large enough to solve a number of interesting computational problems, and it has attractive mathematical properties such as robustness even when mathematical model and input encoding method change.

I am not able to understand completely, how mathematical properties and input encoding are related to defining L complexity class.

The complexity class $\mathsf{L}$ satisfies many desirable properties:

It is closed under concatenation and iteration.
The corresponding function class is closed under composition.
The same complexity class is obtained for any number of work tapes.
It is resilient under "reasonable" input transformations with polynomial blowup (see below).
It can accommodate most known NP-hardness reductions.
It is a subset of $\mathsf{P}$.
It supports pointers indexing the input.

What is an input transformation? Consider the case of graphs. We can encode a graph either as an adjacency matrix of as adjacency lists. We can convert between the two in logspace, and so a graph problem which is in $\mathsf{L}$ under one of them is also in $\mathsf{L}$ under the other.

Logspace is the natural space analog of $\mathsf{P}$, considering the containment $\mathsf{SPACE}(f(n)) \subseteq \mathsf{TIME}(2^{f(n)})$.

It also shows up in the refined Schaefer's dichotomy theorem, as the lowest non-trivial complexity class.


Information theory from a (very pure) mathematician's perspective I'm a pure mathematician interested in learning about information theory. Unfortunately, I'm about as pure as they come - my specialty is mathematical logic, and I have absolutely no experience with programming or anything of a computational nature. I tried looking at Shannon's original paper, but the profusion of numbers intimidated me (I'm a mathematician after all!) When he starts discussing the particulars of coding specific alphabets, my brain begins to asking whether this attention to detail is really necessary and soon zones out... It took Church's thesis for granted some time ago. (Pathetic, I know.)

I'm wondering if there's some introduction to information theory written with people like me in mind. Something which uses the language of measure theory and recursion theory, and works in the greatest generality. Perhaps an expert in the area has written some notes in this direction as an idle folly?

I realize that this might not be the place to ask this question, and apologize if this is the case.

I think you are looking for the topic of "Algorithmic Information Theory" (AIT).
This area is the collision of information theory and computer science. For example "Information and Randomness: An Algorithmic Perspective" written by cristian calude contains interesting subjects in this area. You can find more in the AIT website.


Approximation algorithms for Euclidean Traveling Salesman I am trying to find a way to solve Euclidean TSP in a polynomial time. I looked at some papers but I couldn't decide which one is better. What is the general approximation algorithm for solving this problem in polynomial time?

Euclidean TSP is not even known to be in $NP$, basically because it seems that even to verify if there is a hamiltonian cycle of length at most $k$, we need to computing the sum of square roots. But the problem "$\sum_{i}\sqrt{a_i}<k?$" is not known to be in $NP$.

Anyway Euclidean TSP has $PTAS$.


Show that finding a minimum-weight subgraph that includes all marked nodes is NP-hard We've been given a weighted graph with marked nodes. We want to make a minimum-weight subtree from this graph that contains all marked nodes.

I want to show that this problem is NP-hard. Is there any idea to which problem is the best for reduction to this problem?

This is the problem of finding a Steiner tree in the graph. It's one of the NP-complete problems in Karp's original paper; the reduction there is from Exact cover by 3-sets.


Reduction: Vertex Cover to Binary Integer Program (Decision Problem) I am stuck with the following task:
Show that the Decision Problem "Vertex Cover" is polynomial-time reducible to the Decision Problem "Binary Integer programming".

I have the feeling that there must be a very easy way.

My approach until now:

We can convert any decision problem to an optimization problem in polynomial time.
We can reduce the optimization problem of vertex cover to a linear program in polynomial time. (https://en.wikipedia.org/wiki/Integer_programming#Proof_of_NP-hardness)
We can convert any optimization problem to a decision problem in polynomial time.

Is this approach ok? And/Or is there a better/easier way?

kind regards
James

EDIT: I think the following solution should work

Let $a_{i,j}$ be 1 if vertex $j$ is connected with edge $i$ and otherwise 0. Let $r=|E|$ and $n=|V|$.

A=
\begin{bmatrix}
     a_{1,1} & a_{1,2} & \dots & a_{1,n} \\
     a_{2,1} & a_{2,2} & \dots & a_{2,n} \\
     \vdots & \vdots & \ddots & \vdots \\
     a_{r,1} & a_{r,2} & \dots & a_{r,n} \\
     -1 & -1 & \dots & -1 \\
\end{bmatrix}

Let $b_i = 1$  $\forall i \in 1..r$

b=
\begin{bmatrix}
     b_1 \\
     b_2 \\
     \vdots \\
     b_r \\
     -k \\
\end{bmatrix}

Vertex Cover (Decision Version):

Given a graph $G=(V,E)$ and a positive integer $K$. The decision vertex cover problem asks: Does $G$ contains a vertex cover of size $K$ or less?

Binary Program (Decision Version):

Given a matrix $\mathbf{A}$ of size $m\times n$, a vector $\mathbf{b}$ of size $m$ and a positive integer $L$. Define the decision version of Binary Program as: Is there a vector $\mathbf{x}\in\{0,1\}^n$ of $L$ nonzeros or less such that $\mathbf{A}\mathbf{x}\geqslant\mathbf{b}.$

You could write the optimization version of vertex cover as a Binary Program as follows: Let $x_v$ be a binary variable that is equal $1$ if vertex $v$ is selected, and, $0$, otherwise.

\begin{align}
    & \text{minimize}
    & & \sum_{v \in V} x_v\\
    & \text{subject to}
    & & x_u+x_v\geq 1 \text{ for all } \{u,v\} \in E\\
    & & & x_{ v }\in\{0, 1\}, \forall v\in V.
\end{align}

You can easily check that this Binary Program indeed finds a vertex cover of minimum size.

Now, just set $L=K$, $m=|E|$, $n=|V|$, the vector $\mathbf{b}=[1,1,\ldots,1]^\top$ and the matrix $\mathbf{A}=[a_{ev}]_{\forall\,e\in E,v\in V}$ as

$$a_{ev}=\begin{cases}1,\text{ if } v\in e\\0, \text{ otherwise}\end{cases}$$

This is, cearly, a polynomial-reduction from Vertex Cover to Binary Program.


Why is the size of the search space 2057 in the 8-queen puzzle? In the 8-queen puzzle, to reduce the search space, we can use an incremental approach. We put the first queen in the first column, then the 2nd queen in the 2nd column etc., avoiding the slots that are already being occupied.

According to Peter Norvig's book, there are only 2057 possible sequences. Where does that number come from?

According to Peter Norvig in 2007, it comes from "... writing a program and counting the states."

For the $n$-queens problem, it is not too hard to show that $(n!)^{(1/3)}$ is a lower bound on the size of state space. This can be calculated by considering the maximum number of squares in each column that might be threatened by queens from previous columns. For $n=8$, this evaluates to $34.29$.


Theta estimation of two functions I'm in a data structures class, and am working on an assignment right now that asks me to find the theta complexity of certain loops. I missed class the day we were introduced to the topic, and everything I can find online expects more prior knowledge than I feel I have. Can someone just explain this in beginners terms for me? I don't know what Big-O or theta even refer to in this notation. I think I have a loose idea of what "complexity" refers to (a measure of how efficient code is, depending on how long a function will take in different circumstances?)

The problem in question:

Demonstrate the $\Theta$-complexity of the functions below. In order to demonstrate that $f(n) = \Theta(g(n))$ you must find two constants $C_1$ and $C_2$ such that
$$ C_1g(n) ≥ f(n) ≥ C_2g(n). $$

a.) $f(n) = n^3 - 3n^2 + 5$.

b.) $f(n) = 2\log_2 n - 4$.

The exercise being asked about is pretty stupid (this is criticism against the person who set it as an exercise, not the OP). Every (positive) function $f$ is its own big $\Theta$, that is $f(n) = \Theta(f(n))$. Nevertheless, whoever asked the question expected the following answers: $f(n) = \Theta(n^3)$ and $f(n) = \Theta(\log n)$. There are many online and offline resources that can explain why this is the case and how to prove it, or you can try working through the algebra yourself.

Please let the poser know that the following answers are as mathematically correct as the expected one: $n^3 - 3n^2 + 5 = \Theta(17n^3 - 2n\log n + 4\log\log n)$ and $2\log_2 n - 4 = \Theta(4\log_4 n - 2)$. In order to rule out these answers, the poser should have phrased the question as follows:

  For each of the following functions $f(n)$, find a function $g(n)$ of the form $n^\alpha (\log n)^\beta$ such that $f(n) = \Theta(g(n))$, and prove that $f(n) = \Theta(g(n))$.

Note that in general a function $g(n)$ of that specific form might not exist, for example if $f(n) = n\log\log n$, or for the following more exotic function: $$f(n) = \begin{cases} n & \text{ if $n$ is odd,} \\ n^2 & \text{ if $n$ is even.} \end{cases}$$
Such functions nearly show up in modular exponentiation, FFT-based algorithms, and fast matrix multiplication, though in these cases the difference is only in the constant (e.g. $n$ vs. $2n$) rather than the asymptotics.


Deciding whether a Language is Context-free/Regular/Non Context-Free I need some help with deciding if a given language is regular, context-free or not context-free.

Lets' say I have the following languages over the alphabet $\mathcal{A} = \{a,b,c,d\}$:
$$ \begin{align}
  L_1 &= \{ w \in \mathcal{A}^* \mid \text{\(\#a(w)\) is even and \(\#b(w) = 1 \mathrel{\mathrm{mod}} 3\)  and  \(w \not\in \mathcal{A}^* abc \mathcal{A}^* \)} \} \\
  L_2 &= \{ w \in \mathcal{A}^* \mid \text{\(\#a(w)\) is even and \(\#b(w) \lt \#c(w)\)} \} \\
  L_3 &= \{ w \in \mathscr{A}^* \mid \#a(w) \lt \#b(w) \lt \#c(w) \} \\
\end{align} $$

This is my solution:

$L_1 = L_4 \cap L_5 \cap L_6$ where
$$ \begin{align}
  L_4 &= \{ w \mid \text{\(w\) does not have a substring \(abc\)} \} \\
  L_5 &= \{ w \mid \#a(w) \text{ is even} \} \\
  L_6 &= \{ w \mid \#b(w) = 1 \mathrel{\mathrm{mod}} 3 \} \\
\end{align} $$

A DFA can be constructed for $L_5$, because $L_5$ does not need infinite memory, so $L_5$ is regular. For $L_6$ the same reasoning as above. And for $L_4$ we can construct a DFA that simply does not accept $abc$, hence regular.

$L_1$ is regular because regular languages are closed under intersection.

For $L_2$ we can divide the language thus: $L_2 = L_5 \cap L_7$ where

$$ \begin{align}
  L_5 &= \{ w \mid \#a(w) \text{ is even} \} \\
  L_7 &= \{ w \mid \#b(w) \lt \#c(w) \} \\
\end{align} $$

We now that a DFA can be constructed for $L_5$, hence $L_5$ is regular.
$L_7$ is context-free because we can construct a PDA where the stack counts the number of $a$s and $b$s.

$L_2$ is hence context-free because the intersection of a regular language and a context-free language result in a context-free language.

For $L_3$ we can see that it's not context-free because where are limited to 1 stack.

Is my reasoning right?

Your reasoning for the positive statements seems sound to me, although they lack some detail if formal proofs are required. In particular, you might at least want to give the automata for $L_4,L_5,L_6$ and $L_7$; especially the latter can be considered non-trivial, depending on your level of expertise.

You lack proofs for

$L_2 \notin \mathrm{REG}$ and
$L_3 \notin \mathrm{CFL}$.

Both are true and straight-forward to prove; you find all you need in our reference questions for the regular and context-free case, respectively.


Examples for derandomization via small sample spaces People in theoretical computer science stack exchange advises me to ask this question here. I ask the same problem in https://cstheory.stackexchange.com/questions/46668/examples-for-derandomization-via-small-sample-spaces and if you are interested in answers there, you can go to see it.

I read the book the Probabilistic Method and the lecture note Pseudorandomness to study techniques of derandomization and completed some of exercises.

I'm trying the technique of "Derandomization" for some algorithms, and I find some samples using the derandomization via small sample spaces and feel very interested.

To deepen the impression on derandomization via small sample space, I want to see more papers using that.

There is a survey by Luby and Wigderson: Pairwise independence and derandomization.


Complexity of a loop If the body of a simple for loop has time complexity $O(n)$ and it is
   executed $n-1$ times what is the time complexity of the complete loop?

I am trying to figure out the correct answer to this question for my upcoming exam. My reasoning is that if the body of the loop is executed $n-1$ times and its complexity is $n$ then the complete loop should have time complexity of $O(n \times (n-1)) = O(n^2 - 2) = O(n^2)$.

However, the correct answer given to us is $O(n^3)$.
Am I missing something or is it just a mistake in the answers?

Edit: It turns out that the answer given to us was just wrong...

As mentioned, the body of the simple loop is run in $O(n)$. As a loop iterates over the body $n$ time (probably), the time complexity of the loop is $O(n^2)$. When you run the loop $n-1$ times, the time complexity would be $O(n^3)$.


Binary Tree Node Insertion I was trying to implement a Binary Search Tree using this article as a reference: Binary Search Tree in JavaScript.

I was thinking especially about the node insertion method. Here's my implementation:

class BinaryTree {
// ... initialization
add(val) {
    if(this.root === null) {
        this.root = new Node(val);
        return ;
    }
    this.addNode(val, this.root);
}
addNode(val, node) {
    if(!!!this.comparator) throw new Error('this.comparator cannot be undefined.');
    let comp = this.comparator(val, node.val);
    if(comp === -1) {
        if(node.left === null) {
            node.left = new Node(val);
            return ;
        }
        this.addNode(val, node.left);
    }
    else if(comp === 1) {
        if(node.right === null) {
            node.right = new Node(val);
            return ;
        }
        this.addNode(val, node.right);
    }
}
// ... other methods
}

where this.comparator = (v1, v2) => { return (v1 <= v2) ? -1 : 1; };

My questions are:

Is there a way to modify this add method such that it can balance the tree after every addition?
If so, by factor would the time complexity of add be growing?

Search & read on AVL trees that follow the BST rules while keeping a worstcase balance difference of 1 between subtrees.
read  knuth sorting & searching


Detecting cycles in undirected graph I want to detect cycles in an undirected graph such that I get a list of all edges/vertices which form each cycle. For a graph G({a,b,c,d}, {a-b, b-c, c-d, d-a, b-d}) this would be {a, b, c, d}, {a, b, d}, {b, c, d}.

I have read this and I think that when the iterative pseudocode from Wikipedia finds a back-edge then I can say the graph has a cycle. But I don't know how to find out which vertices/edges the cycle consists of.

Can you please help with an algorithm which would take a graph as input (or the information from DFS) and output list of lists describing the cycles?

You're almost there, but when you find a back edge you already have all the information you need to describe the cycle it forms. Also, there's a bit of a complication where you might find duplicate cycles. Or you might not. Do you consider {A, B, C} to be the same cycle as {C, B, A}? What about {B, C, A}? Depends on what you're doing, but let's assume they're equivalent.

So you've got a graph you're DFSing.
illustration http://imageshack.us/a/img687/1598/tjd.gif.

And you go down one branch and detect a few cycles. Cool.
illustration http://imageshack.us/a/img14/9295/4bo.gif

But you haven't explored all possibilities, so you unwind the stack and take the next branch. You find some more cycles. Groovy.
illustration http://imageshack.us/a/img818/3851/t69.gif

The adventure continues. You go down another path and find another cycle. Good.
illustration http://imageshack.us/a/img543/48/c5mb.gif

No, wait. BAD. You've got two equivalent cycles. And when you unwind to having only explored A-B, and take A-B-E this time, that's going to reveal more duplicates. You'd need a way to get rid of those, if they are a problem in your application.


how to prove original intervals and canonical form of intervals have the same interval graph According to this paper,a family of intervals is said to be canonical if the coordinates of the endpoints of the intervals are distinct integers between 1 and 2n where n is the number of intervals.

Here is the example
Original intervals = {[2,5], [3,11], [6,9], [7,13], [8,18], [12,16], [15,19]}

Canonical form of intervals = {[1,3], [2,8], [4,7], [5,10], [6,13], [9,12], [11,14]}

These original intervals and canonical form of the original intervals give the same interval graph, but how can I prove that it is always the case mathematically ?

Edit: This is the method I use to create canonical intervals:
I sort the intervals according to their starting points in ascending order
Then, I assign the first interval's [2,5] starting point as 1. Then, I compare it with the following intervals to see the overlappings. Then, I arrange the intervals accordingly.

I repeat this process for all intervals.

Examples:

[2,5] contains only the starting point of interval 2, so

[2,5] becomes [1, (start of interval 2), 3] = [1,3]

[3,11] contains, start of interval 3, start of interval 4, end of interval 3, and start of interval 5, so

[3,11] becomes [2, 3, (start of interval 3), (start of interval 4), (end of interval 3),(start of interval 5),8] = [2,8]

note: interval 2 can not start here because at point 3 because it is where interval 1 ends. All start and end points should be distinct.

You haven't described how a system of intervals are converted to canonical form, but here is one way to do it. We find an order-preserving mapping (satisfies $f(x) < f(y)$ iff $x < y$) from the coordinates in the original system to the integers $\{1,\ldots,2n\}$ (we do this by sorting all of the original coordinates). We get the same interval graph since the mapping is order-preserving – that's a nice exercise.


Non-quadratic search for specific difference between elements in sorted array New to computer science and am attempting to verify if there are any non-quadratic approaches (i.e. better performance than Big-O of n^2) for finding a potential specific difference between either adjacent or nonadjacent elements in a sorted array of integers?

For example, if you have an array that's already been sorted, like so:

[1, 4, 6, 6, 10, 12, 13, 15, 16]

And you want to find if there's a difference between any of these elements that equals 3, the pairs here would be 4, 1 and 15, 12 and 13, 10.

But is there an algorithmic approach that would allow me to find these pairs without using two for loops?

I know of two.

Sort the numbers, then walk 2 pointers from opposite ends towards each other, moving the left pointer rightward whenever the difference of the pointed-to elements is too small, and the right pointer leftward whenever it is too large; the invariant here is that any satisfying pair must be taken from the interval of elements spanned by the 2 pointers.
Build a hash table containing every element as key (the value for each key is unimportant), then loop through every element $x$
again, checking whether $x+d$ or $x−d$ is in the hashtable.


Can we do 4-sum algorithm in O(n^2)? this is related to the following question:

Generalised 3SUM (k-SUM) problem?

Without loss of generality, let's only consider even $k$, or just $k=4$.

My question is, after summing all pairs of numbers, is it necessary to sort the list of sums? I understand we could use two pointers from left and right to sandwich the two pairs in $O(n^2)$ time, but the sorting requires $O(n^2\log(n))$ time.

If we use a hashmap to store the sums as key and their corresponding index pairs as value, then all operations can run in $O(n^2)$ time.

Am I missing something in that post or is it true for even $k$, $k$-sum can run in $O(n^{k/2})$ time?

Thanks!

You are right, but Jeff's answer in the link you provided works in the "linear decision tree model". You cannot use hashing in that model.


optimal lifted phylogenetic alignment - how to improve time complexity? optimal lifted alignment - is a dynamic programming algorithm. Its input is a tree $T$ with $k$ strings assigned to its leaf nodes (their length is $n$).

The algorithm then assigns strings to the internal nodes s.t. the sum of distance (global alignment distance) on all the edges would be minimal, under the constraint that the string assigned to each node is one of the strings of its immediate children (hence the name "lifted").

The algorithm first computes distances $D$ between all pairs $O(k^2n^2)$. For each leaf node $v$ assigned $S_v$ we initialize: $d(S, v) = 0 | S = S_v$ and $d(S, v) = \infty | S \neq S_v$.

We then traverse post-order and for each internal node $v$, for each string $S$ assigned to one of its leaf descendants (all strings in its subtree) does $d(v,S) = \sum{\min(D(S,T) + d(w,T))}$ where $w$ are $v$'s immediate children. Overall = $O(k^2n^2 + k^3)$.

I've been told its possible to improve the complexity to $O(k^2n^2 + k^2)$ but I can't see how? Would appreciate any hint.

Consider a node $x$ with children $x_1,\ldots,x_d$, and denote by $N(v)$ the number of leaves in the subtree $T(v)$ rooted at $v$. We can implement the processing of $x$ as follows:

Go over $1 \leq i \leq d$:

Choose a leaf $f_i \in T(x_i)$ as the label of $x$ and $x_i$.

For all $j \neq i$, choose the leaf $f_j \in T(x_j)$ that minimizes $D(f_i,f_j) + d(x_j,f_j)$.

Store $d(x,f_i) = \sum_{j \neq i} [D(f_i,f_j) + d(x_j,f_j)]$.

The processing time of $x$ is proportional to
$$
\sum_{i=1}^d N(x_i) \times \sum_{j \neq i} N(x_j) = \left(\sum_{i=1}^d N(x_i)\right)^2 - \sum_{i=1}^d N(x_i)^2 = N(x)^2 - \sum_{i=1}^d N(x_i)^2.
$$
Summing over all nodes $x$ up to the root $r$, we see that the total processing time is proportional to $N(r)^2 = k^2$.


Example of graph with exponential many s-t minpaths and min cuts I am trying to find a graph in which both s-t minpaths and min cuts are exponential.

Individually I found examples in which s-t minpaths and s-t min cuts are exponential. Can some one provide me an example of graph which has both min paths and min cuts in exponential size.

I can offer an example for super-exponentially many shortest paths and super-polynomially many minimum cuts.

An example for many shortest s-t-paths you probably came up with is the layer graph, similar to the one here. Turns out we can use the same idea here -- all we have to do is use many layers so that there are many minimum cuts, and fiddle with the weights so that there have to be enough "inner" nodes in either partition.

Idea: Use a complete layer graph with $\sqrt{n}$ layers and $\sqrt{n}$ nodes in each layer. Add $s$ and $t$ and wire with the first resp. last layer; make the weights on these edges so large that the first layer has to be in the partition of $s$ (and the last in that of $t$) for every minimum cut.

The graphs look like this (unit weights on all unlabelled edges):

[source]

Now we can count.

The graph has $n + 2$ nodes and $(n+2)\sqrt{n} - n \in \Theta(n^{\frac{3}{2}})$ edges.
Every shortest s-t-path picks one node in every layer; hence, we get $\sqrt{n}^{\sqrt{n}}$ such paths.
No edge $(s,\_)$ or $(\_,t)$ is ever part of a minimum cut (each such edge has more weight than all others together). Convince yourself that all cuts constructed by fixing a column (but the first and the last), putting every node either left or right and using this as the "cut line", are minimal with weight $n$. We obtain $(\sqrt{n}-2) \cdot 2^{\sqrt{n}}$ many such cuts.

At least with layer graphs, I think the two quantities can not be exponential at the same time; one needs non-constant depth, the other linear width. I'm not sure if a similar argument carries over to general graphs.


Information theory of instruction set architecture design? Information theory to a large extent deals with how to efficiently encode messages given a probability distribution over messages.

Intuitively, it seems like we can think of machine instructions (or programs) as "messages to the CPU". Some messages are more probable than others. E.g. "add numbers x and y" is more probable than "compute the y'th square root of x", which is maybe one of the reasons why we don't have an instruction like the latter.

However there are obviously other considerations involved like computational complexity, so it doesnt seem obvious to me how information theory can be used to understand instruction set architectures. Has information theory been apllied to understand insteuction set archtectures? (I didnt find anything after a quick google search.)

It seems you are interested in how to represent instructions in the most compact size. But that is quite a secondary consideration.
The most important two considerations are: 1. Being able to decode an instruction in the shortest possible time. 2. Determine the length of an instruction in the shortest possible time.
Why is this so important? Let's say you have an instruction to add two integers. This can be done very fast, say 300 picoseconds. Now when you decode that instruction, the decoding must be done in a time comparable to that of an addition, or the decode time becomes what limits the speed of your CPU, instead of the time that is actually needed to do the work.
The time to determine the length of an instruction is even more critical. Modern CPUs will often execute up to four instructions per processor cycle. So they must be able to decode four instructions per cycle. To do that, they must be able to determine the length of the first instruction, the second instruction, and the third instruction, before they can figure out where the fourth instruction starts, and start decoding that instruction. So we need to determine the length of three instructions, and decode a fourth, in the time it takes to add two integers!
So you can see how decoding must be absolutely fast. You just don't have the time to use any decent compression algorithm because it would slow down everything.
Update: ARM processors with fixed instruction length can decode 9 instructions per cycle, while variable length x86 instructions are limited to 4 decodes per cycle. So this is not something that can be solved by throwing transistors at the problem.


When our two-state PDA constructed from CFG is non-deterministic PDA? We can always convert our GNF-CFG/CNF-CFG to a two-state PDA but i'm wondering when our PDA is non-deterministic? i'm sure we can not make DPDA for non-Deterministic-CFL , and i suspect that same rule which applied for differing between DCFG and non-Deterministic-CFG also applied here. i mean when we have non-Deterministic δ (delta) implied non-Deterministic edge in our PDA. if my suspicion is right , then for every DCFL exist at least one DPDA with two state. Am i right?

R ≝ Production Rules of CFG
(x,y,"LBL") is a labeled-edge between x and y with “LBL” as a label
∀r∊R: r= (A,aⱰ) ( A∊V ⋀ a∊T ∧ Ɒ∊V*) add (q,q,"a,A/Ɒ") to E
Add (q,q,"ε,z/Sz′") to E
Add (q,f,"ε,z′/z′") to E

Your construction starts with a CFG $G$ in Greibach normal form. So each of the productions of $G$ is of the form $A \to a \alpha$, with $A$ nonterminal, $a$ terminal and $\alpha$ a string of nonterminals. Such a production is then directly translated into a PDA instruction $(q,a,A) \mapsto (q,\alpha)$. "read $a$ from the tape, pop $A$ and push $\alpha$"

In general PDA is deterministic if there is no configuration in which two different instructions can be applied. So, no two instructions in the same state, the same input symbol, and the same top of stack. Looking back at the CFG that means there are no two productions of the form $A \to a \alpha$, $A \to a \alpha' $, with $\alpha\neq \alpha' $.
If there are two such productions, then in configuration $(q,aw,A\gamma)$ - state $q$, string $aw$ to be read, and $A\gamma$ on the stack, the PDA can make to moves, pushing $\alpha$ or $\alpha'$.

This analysis is not complete. There are two additional instructions  $(q,\varepsilon,Z) \mapsto (q,SZ')$ ("on initial stack symbol $Z$ push the axiom of the grammar") and   $(q,\varepsilon,Z') \mapsto (f,Z')$ ("when the stack is empty, derivation has ended, move to final state"). Although these are $\varepsilon$ instructions, they can only be applied when none of the CFG rules is applicable (start and end) so they will not cause nondeterminism.


How to find the nearest point in the coordinate system There are so many points in the coordinate system. When a specific point is given in the coordinate system, I want to find the closest point to the straight line distance. For example, if you have 800 points, calculate the distance 800 times and find the smallest value. But I want to make more efficient algorithm that doesn't execute 800 times due to that it might be sorted in a certain order before searching.
That is, if the points is put in a certain order,
 Could you recommend some notions?

So, if I understand correctly, you have a set $S$ of points in some space (do you have a specific dimension ?), and a point $x$, and you want to find the point of $S$ that is the closest to $x$ ?

If this is indeed what you are trying to do, have a look at K-d trees and Voronoï tesselation. These methods are based on space partitioning to make queries faster.


Examples of specialized instructions of assembly language not available in compilers? In my CS computer organization textbook, there's this blurb on the advantage of assembly over a high-level language.

  Another major advantage of assembly language is the ability to exploit specialized instructions - for example, string copy or pattern-matching instructions. Compilers, in most cases, cannot determine that a program loop can be replaced by a single instruction. However, the programmer who wrote the loop can replace it easily with a single instruction.

How can a loop be replaced by string copy or pattern matching? Can somebody give an example on specialized instructions that are not available in a high-level language and how a specialized instruction can replace a loop?

Counting bits set, Brian Kernighan's way

unsigned int v; // count bits set (1)
unsigned int c; // result
for (c = 0; v; ++c)
{
  v &= v - 1;
}

This code becomes popcnt


Data Structure with multiple indexes Apologies if a duplicate. New to this community and did try to search.

I want to create a mapping document that equates defect severity levels together so it looks like

|| System 1 || System 2 || System 3 ||
| level1-1 | level1-2 | level1-3 |
| level2-1 | level2-2 | level2-3 |

So that I can effectively do a lookup with a key of "level2-2" and get the row back. Similar I guess to a SQL row and being able to match on a column

Is there a name for this data structure?

There are many data structures you could use for this purpose.

One possibility is a relational database (just like you've shown).

Another possibility is any data structure for storing equivalence relations; for instance, the standard Union-Find data structure would do.  Here you'd be storing that (System 1, level1-1) is equivalent to (System 2, level1-2), and so on.  That would work, too.

[ General advice for asking in the future: Don't worry too much about "names" for something.  Names matter a lot less than finding a reasonable solution.  Instead, think of the task you're trying to accomplish, what your requirements are, what you're trying to optimize, and then ask how to do that. You might get back an answer that says "read up on this standard thing"; or you might get back an answer that just directly describes a solution to your problem.  Either way, you win! ]


Question on synchronisation The following two functions P1 and P2 that share a variable B with an initial value of 2 execute concurrently.

P1() {

    C = B - 1;
    B = 2 * C;
}

P2(){

    D = 2 * B;
    B = D - 1;
}

The set of distinct values that B can possibly take is ?
My understanding: Say P1 executes first , then B=2, after that P2 executes next  then value of B=3.  Again P1 executes and we get B value as 4, yet again B executes and we get B value as 7 etc. So does this mean B will take up infinitely many values?  The order of my execution is P1-P2-P1-P2-P1.... Is this correct?

Label the four statements
$$\begin{align}
x &: C=B-1\\
y &: B=2C\\
z &: D=2B\\
w &: B=D-1
\end{align}$$
The only constraint is that $x$ must be executed before $y$ and $z$ must be executed before $w$, giving us six possible orders: $xyzw,xzyw,xzwy,zxyw,zxwy,xwzy$. Trace the execution of each of these possible orders and you'll find that $B$ can have a final value of $2$ (twice), $3$ (three cases), and $4$ (in one case).

For what it's worth, if P1 consists of $n$ assignments and P2 has $m$ assignments, the total possible orders is given by the binomial coefficient $\binom{n+m}{n}$, though that won't necessarily be the same as the number of possible final values of the shared variable $B$.


Do not understand a lemma regarding dinics algorithm Here you can find the following lemma with its proof.

Lemma: In a network with unit edge capacities,
Dinitz algorithm terminates after $O(\sqrt{m})$
blocking flow computations.

Proof:
Consider the layered network after $\sqrt{m}$ iterations.
It has at most m edges. The average number of
edges between any two layers is $\frac{m}{\sqrt{m}} = \sqrt{m}$.
Hence, there must be at least one layer $i$ with
at most $\sqrt{m}$ edges. Now consider the cut
$S=\{v | level_f(v) < i\}$. It has capacity at most $\sqrt{m}$.
Since each blocking flow augmentation increases flow
by at least one, after $\sqrt{m}$ additional blocking
flow augmentations,  a maximum flow has been found.
Hence, no more than 2$\sqrt{m}$ = $O(\sqrt{m})$
blocking flow augmentations are needed.

I don't understand the proof. The layered graph $G_{L}$ has m edges. But how does it look like after $\sqrt{m}$ iterations? Is the average number of edges of $G_{L}$ between any two layers $\frac{m}{\sqrt{m}} = \sqrt{m}$ after $\sqrt{m}$ iterations? And the confusion continuous with the set $S$.

Could someone unfold this proof for better understanding?

"How does it look like after $\sqrt{m}$ iterations?"

To see this, we need a property: the number of layers increases by at least $1$ after each iteration.  In other word, the shortest distance from $s$ (source) to $t$ (sink) increases by at least $1$. This is the key property of Dinic's algorithm. I'll put the proof at the end. (Please help if anyone has a better way to arrange these contents. I don't want to let the proof occupy too much space.)

So after $\sqrt{m}-1$ iterations, $G_L$ has at least $\sqrt{m}+1$ layers, because there are at least $2$ layers at first, one for $s$ and one for $t$. This means there are at least $\sqrt{m}$ "edge layers" between the vertex layers. So the edge layer with the least number of edges has at most $\frac{m}{\sqrt{m}}=\sqrt{m}$ edges. One more thing you should notice is this edge layer forms a $s$-$t$ cut in the residual graph with capacity at most $\sqrt{m}$. (You can't jump across any layer, so you must pass this layer.) According to max-flow-min-cut theorem, capacity of maximum flow in the residual graph is at most $\sqrt{m}$. So we need at most $\sqrt{m}$ more iterations. In conclusion, the total number of iterations is $O(\sqrt{m})$.

Proof of the key property:

Suppose at some iteration we have residual network $G_f$ and its corresponding level graph $G_L$, and after one iteration we have residual network $G_f'$. To prove that $s$-$t$ distance in $G'_f$ is longer, first let's see the difference between $G_f$ and $G_f'$: if an edge $(u,v)$ is saturated, $(u,v)$ is removed and $(v,u)$ is added. Note that the blocking flow only contains edge in $G_L$, so $(u,v)$ is a "foward" edge in $G_L$, and $(v,u)$ is a "backward" edge in $G_L$. Here "forward" means the edge moves from lower level to higher level in the level graph.

Consider a shortest path from $s$ to $t$. Each edge $e$ on this path has three possibilities:

$e\notin G_f$. In this case $e$ is new, so it's "backward" in $G_L$ according to our claim above.
$e\in G_f$ but $e\notin G_L$. In this case, $e$ can't be forward. Otherwise it would be contained in $G_L$. (Note that a forward edge can't jump across a layer because the level graph is constructed based on shortest distance.)
$e\in G_L$. This is the only possible forward edge, which increases the level by exactly $1$.

Consider the level in $G_L$ of each vertex on the $s$-$t$ path. The level increases by at most $1$ after each step. So the shortest path from $s$ to $t$ in $G_f'$ is never shorter than the shortest path in $G_L$. Furthermore, it should be strictly longer: if the distance is the same, it means the shortest path in $G_f'$ only consists of type $3$ edges. This means we can find an unsaturated path in $G_L$, which violates the definition of blocking flow.

Therefore, the number of layers is strictly increasing.


Is the ability to do depth first search a proof of Turing Completeness? Can we write a non-TC automaton that does DFS? As the title states. Let's say we have a set of inputs that define a tree structure. Is it possible to construct an automaton that can perform depth-first search on this data that is not Turing-complete? If so, can we state that the ability to do DFS a sufficient proof of Turing-completeness?

For the purpose of the question, you can have some leeway about how the data is represented. As long as you can come up with a combination of a tree representation and an automaton that can DFS it that is less than Turing-complete, that's good enough. If it simplifies anything, you can make assumptions about the nature of the tree (e.g. binary or not), but a more generalizable answer would be preferred.

Most functions you'll ever deal with in practice are primitive recursive, a model of computation that is properly less powerful than TMs.

More specifically, the problem from the question can be implemented on linear-bounded automata (LBA), a model of computation that is equivalent with context-sensitive grammars -- properly less powerful than TMs.


Computing composite functions This may not be strictly a computer science question but is related.

Whenever there is some function that computes more than two elements, is it possible that all elements are computed at once? Or is computing in composite/series a required limitation of the brain?

For instance, to add three numbers, we add two and then and the third to the result of the first addition. Is it possible for the brain to take all three numbers and process them at once with no intermediate step? Is it possible for machines? Is it possible with quantum computing?

In the case of the brain's inability to make this computation, is it because we are trained to compute in a certain way or is it an inherent limitation?

Definitely possible for a computer, since three-input logic gates exist.   Possible for humans too, at least as far as conscious operations are concerned.  If you show me a partition of 13 into no more than 4 parts (e.g. 5+3+4+1), I can recognize it without any intermediate calculation simply from long experience playing bridge.


Flaw in my NP = CoNP Proof? I have this very simple "proof" for NP = CoNP and I think I did something wrongly somewhere, but I cannot find what is wrong. Can someone help me out?

Let A be some problem in NP, and let M be the decider for A. Let B be the complement, i.e. B is in CoNP. Since M is a decider, you can use it to decide B as well (just flip the answer). Doesn't that mean that we solve both NP and CoNP problems with the same M?

To put it more concretely.

Let A be some NP-complete problem, and let M be decider for A. Consider any problem B in CoNP. We consider its complement not-B, which is in NP, and then get a polynomial reduction to A. Then we run our decider M and flip our answer. We thus obtain a decider for B. This implies B is in NP as well.

May I know what is wrong with my reasoning?

There are two possible bugs in this proof:

When you say "decider" - you mean a deterministic TM. In this case, the best translation (to our knowledge) from an NP machine to a deterministic machine may yield a machine that runs in exponential time, so after complementing you will have a decider for the complement in exponential time, proving that $co-NP\subseteq EXP$ (or, after some optimization, $co-NP\subseteq PSPACE$).
When you say "decider" you mean a nondeterministic TM. In this case, flipping the answer will not necessarily complement the language. Indeed, the language of the flipped machine will be all the words for which there exists a rejecting run of $M$ on $w$


Can a computable function converge to an uncomputable number? Does there exist a computable function $f:\mathbb{N}\rightarrow \mathbb{Q}$  such that:

For all $t\in\mathbb{N}: 0\le f(t) < X$
$\lim\limits_{t\rightarrow\infty} f(t) = X$

Where $X$ is an uncomputable real number.

The only reference to this question I have found was the answer to this question: https://math.stackexchange.com/a/1052579/168764, where the function seems that it would hold, but I have no idea how to prove that the limit of this function is an uncomputable real number.

Consider the real number encoding of the (almost) halting problem, i.e. $0.r_1r_2...$ where  $r_i=1$ if the i'th Turing machine (relative to the lexicographic ordering) halts on the empty input, and $r_i=0$ otherwise. Let us denote this number by $R$.

Now, consider the machine $M$ which on input $n$ simulates all Turing machines of length $< n$ on the empty input for $n$ steps, and returns $0.\hat{r_1}...\hat{r_{2^n-1}}$ where $\hat{r_i}=1$ if the $i$'th Turing machine halts on the empty input in less than $n$ steps, and $\hat{r_i}=0$ otherwise. Clearly for all $n$ it holds that $M(n)< R$, and it is not too hard to show that $\{M(n)\}_{n\in\mathbb{N}}$ converges to $R$. The key point is that rate of convergence is not computable, meaning that given $\epsilon$, you cannot compute the index such that beyond it the series is $\epsilon$-close to $R$.


One tape nondeterministic Turing machine accepting non-palindromes I have to design a nondeterministic one tape Turing machine that accepts only non-palindromes in $O(n \log n)$ time.
My best shot was only in $O(n^2)$ time. How can I use the properties of NTM on a single tape to find a faster solution?

Hint: to prove that a string $x_1x_2\cdots x_n$ is not a palindrome, we only need a value $i$ for which $x_i\neq x_{n+1-i}$.


How not to solve P=NP? There are lots of attempts at proving either $\mathsf{P} = \mathsf{NP} $ or $\mathsf{P} \neq \mathsf{NP}$, and naturally many people think about the question, having ideas for proving either direction.

I know that there are approaches that have been proven to not work, and there are probably more that have a history of failing. There also seem to be so-called barriers that many proof attemps fail to overcome.

We want to avoid investigating into dead-ends, so what are they?

I'd say the most well known barriers to solving $P=NP$ are

Relativization (as mentioned by Ran G.)
Natural Proofs - under certain cryptographic assumptions, Rudich and Razborov proved that we cannot prove $P\neq NP$ using a class of proofs called natural proofs.
Algebrization - by Scott Aaronson and Avi Wigderson. They prove that proofs that algebrize cannot separate $P$ and $NP$

Another one I'm familiar with is the result that no LP formulation can solve TSP (It was proved by Yannakakis for symmetric LPs and very recently extended to general LPs). Here is a blog post discussing the result.


Multi-threading vs. Interrupt Handlers In Arduino's architecture, multi-threading is not supported. However, interrupt handlers are being used as "placebo/replacement" if you may. However, I am not quite sure how these interrupt handlers work. For instance:

void functionA()
{    //x is a global boolean
    x = true; //as soon as this is set to true, before the next line executes, it jumps to functionB
    int y = 10;
}
void functionB()
{
    while(x) executeSomeOperation;
}

Something of that sort takes place(forgive my crude code, it is just to get my point across). More specific examples can be found in the VirtualWire library of Arduino. How is that possible without multi-threading? Because as function A is taking place, the program must surely be waiting to see if x is being set to true. Which sounds like "multi-threading" to me. Thus, can someone clarify the differences between how multi-threading and interrupt handlers work?

Threads
On a platform that supports multi-threading the threads run in parallel.
That means that multiple threads can run at the same time.
This depends on the numbers of cores the CPU makes available.
If the programmer insists on running more threads than the CPU has cores then the threads will be time-sliced.
How much time each thread gets depends on the priority of that thread.
A thread can also choose to yield, which means that it will transfer execution time to another thread before its time slice is up.
If a thread does not yield the scheduler (which is part of the operating system) will pause the thread and force another thread to run.

Interrupt handler
An interrupt handler interrupts the main program. That means that the state of the thread is saved and execution is paused.
The interrupt handler is executed and when the interrupt handler yields the state of the main program is restored and execution of the main program resumes.

In many systems the interrupt handler is assigned a standard interruption schedule, e.g. 50 times a second.
The interrupt is always given preference over the main program, so if the interrupt takes up a lot of time the main program will get very little or no time to run. The interrupt gets scheduled no matter what. The main program gets whatever time is left over.
An interrupt handler is not subject to a scheduler, although possibly the interrupt can be interrupted by another interrupt.

Time slicing
In contrast, threads (insofar as threads outnumber CPU cores) are time sliced. Every thread gets the same amount of time. If there is a high priority thread it may get more time or get scheduled more often, but the scheduler makes sure every thread does get a time slot now and then.

Interrupts don't play nice
Because an interrupt handler will get prioritized over the main execution it is unwise to treat it like a thread. If you do heavy calculation in an interrupt handler your main program will never run!
This is made worse by the fact that interrupts are usually scheduled to run many times a second.

Alternatives
There is an alternative to abusing the interrupt handler for multi-threading.
You can use fibers on Arduino.
Fibers are cooperative threads, that means that a single thread will run until it yields.
After a yield the next fiber in line will run.
As long as all fibers yield in a cooperative manner this works very much like real pre-emptive threads.
If one fiber does not yield, none of the other fibers will get any running time.
This is the multi-tasking mechanism that was used in Windows 3.x

Just to make things confusing libraries that support this behavior talk about threading, not fibers.
Note that threading is impossible on Arduino, so these misnamed 'threads' are really fibers.


Influence of the dimension of cellular automata on complexity classes Let's take as an example the 3d → 2d reduction: What's the cost of simulating a 3d cellular automaton by a 2d cellular automaton?

Here is a bunch of more specific questions:

What kind of algorithms will have their time complexity changed, by how much?
What would be the basic idea for the encoding; how is a 3d grid efficiently (or not efficiently…) mapped to a 2d grid? (The challenge seems to achieve communication between two cells that where originally neighbors on the 3d grid, but are not neighbors anymore on the 2d grid).
In particular, I'm interested in the complexity drift for exponential complexity algorithms (which I guess remains exponential whatever the dimension, is it the case?)

Note: I'm not interested in low complexity classes for which the chosen I/O method has an influence on complexities. (Maybe the best is to assume that the I/O method is dimensionless: done locally on one specific cell during a variable amount of time steps.)

Some context: I'm interested in parallel local graph rewriting, but those graphs are closer to 3d (or maybe ωd…) grids than to 2d grids, I'd like to know what to expect of a hardware implementation on a 2-dimentional silicon chip.

I will explain pieces of this article: Simulating 3D Cellular Automata with 2D
Cellular Automata.

Let's start by the encoding of the grid, a function $t:\mathbb Z^3 → \mathbb Z^2$. Intuitively $t$ can't preserves the distance because the number of cells at a distance less than $R$ from the origin won't be the same. You will need to embed these about $R^3$ cells into some the same number of cells but which will be somehow of the form $r^2$ but then you must have $r>R$. These $r$ and $R$ are a bit like the radius of the notion of neighborhood you find in any cellular automaton.

So the transformation of the article will make things essentially bigger by a power of at least $3/2$. That if points are distant of $d$ in the first grid, they will be distant of at least $O(\sqrt d^3)$ in the second grid. Unfortunately the given embedding is only in $O(d^3)$.

However, and this is a very important remark, you don't obtain the same neighborhood than in the first automaton and that's why I previously said "a bit like". To quote the article:

  it is obvious that there will be cells that are very close in $\mathbb Z^3$ and such that [their encoding will be] arbitrarily far in $\mathbb Z^2$

That works for time, too: the execution time of one step in $\mathbb Z^3$ can be arbitrary long in $\mathbb Z^2$. Note that the encoding is more of a simulation: the 2D CA the author even simulates the computation of the function $t:\mathbb Z^3 → \mathbb Z^2$.

It is a safe bet to say that the complexity (in time) of any algorithm ran on a 3D CA will explode when ran on the encoding of this 3D CA into a 2D CA. The author says it cannot be bound by any function in his simulation. And I say the explosion is at least exponential in general, because of the propagation time of the information depends on the position.

The idea of running algorithms on cellular automata seems already a bit weird to me, but that's personal. However that's nothing compared to the idea of an implementation of a cellular automaton into a silicon chip, or is it just me?


What is the asymptotic running time of the following piece of code? I am working with this problem:

What is the asymptotic running time of the following piece of code?

if (N < 1000)
   for (int i = 0; i < N*N*N; i = i+1) A[i] = j;
else if (N < 10000)
   for (int i = 0; i < N; i = i+1) A[i] = j;
else
  for (int i = 0; i < N*N; i = i+1) A[i] = i;

Where the possible answers are:

A) linear in N
B) linearithmic in N
C) cubic N
D) quadratic in N

I am unsure how to calculate it, but when I look at the code I think A and B is not the right answer, because of the for-loops multiply with the variable x-times. If possible, could someone also explain what "Asymptotic time" means?

An easy way to intuit asymptotic notations goes like this. Say you have a number $n$ and a constant $c$. Now $n^2$ will always be greater than $n*c$ for any choice of $c$ where $c < n$. So no matter what the constant coefficient is, it will never exceed $n^2$.

Now your question. Asymptotic notations are calculated for sufficiently large values of n where sufficiently large is usually taken as infinity. So although your algorithm has $n^3$ and $n$ time complexities for smaller values of $n$, for large values ($n$ tends to infinity), the time complexity is $n^2$.


Why does a range query on a segment tree return at most $\lceil \log_2{N} \rceil$ nodes? If an array $A[1 \ldots N]$ is represented using a segment tree having sets in each interval, why does a range query $[L\ldots R]$ returns at most $\lceil \log_2{N} \rceil$ sets (or disjoint intervals)?

If came across this statement while reading this answer.

To quote:

  Find a disjoint coverage of the query range using the standard segment
  tree query procedure. We get $O(\log n)$ disjoint nodes, the union of
  whose multisets is exactly the multiset of values in the query range.
  Let's call those multisets $s_1, \dots, s_m$ (with $m \le \lceil \log_2 n \rceil$).

I tried searching for a proof, but couldn't find it on any site. Can anyone help me prove it?

Here's the basic idea.

Let a dyadic interval be an interval of the form
$$ [2^b a,2^b(a+1)-1] $$
for some integer $a,b \geq 0$.

Claim 1. If $m < 2^n$ then any interval of the form $[0,m-1]$ can be written as the disjoint union of at most $n$ dyadic intervals.

Proof. Expand $m$ as a sum of decreasing powers of 2:
$$ m = 2^{a_1} + \cdots + 2^{a_k}. $$
Then we can write
$$
[0,m-1] = [0,2^{a_1}-1] \cup [2^{a_1},2^{a_1}+2^{a_2}-1] \cup \cdots \cup [2^{a_1} + \cdots + 2^{a_{k-1}},2^{a_1} + \cdots + 2^{a_k}-1].
$$

Claim 2. If $0 \leq m_1 \leq m_2 \leq 2^n$ then any interval of the form $[m_1,m_2-1]$ can be written as the disjoint union of at most $2n$ dyadic intervals.

Proof. The binary expansion of $m_1$ and $m_2$ is of the form $m_1 = x0y, m_2 = x1z$, where $|y|=|z|$. Let $m = x10^{|z|}$. Using Claim 1, we can express $[0,m_2-m-1]$ as a union of at most $n$ dyadic intervals. Shifting these by $m$, we express $[m,m_2-1]$ as a union of at most $n$ dyadic intervals. Similarly, using Claim 1 we can express $[0,m-m_1-1]$ as a union of at most $n$ dyadic intervals. Shifting and inverting, we express $[m_1,m-1]$ as a union of at most $n$ dyadic intervals.

(In both cases, one needs to check that shifting, and possibly inverting, preservers an interval being dyadic.)


Are consensus (and atomic broadcast) protocols limited by single node's resources? The main question is the following:
When designing a system supporting atomic broadcast, can it be proved theoretically that the performance & scalability dimensions (i.e. latency, throughput, dataset size) of the system are limited by the performance of a single node?

To give an example:
A system based on partitioned-logs, like Apache Kafka, can provide ordering guarantees in a single partition, but it can't provide any ordering guarantees between different partitions. However, this gives Kafka the capability to scale to extremely large datasets. I was contemplating whether it would be possible to create a system that could provide the ordering guarantee for the whole dataset, while also allowing the dataset's size to increase in the same quasi-linear way.

My speculative answer to this is no for the following reason:
It's been proved that the atomic broadcast problem is equivalent to the consensus problem [1]. Based on the fact that the consensus problem requires an elected leader, which drives the consensus process, I concluded that the scaling capabilities of such a system is limited by the resources of a single node.

Are there any flaws in my thinking ?

[1]: https://en.wikipedia.org/wiki/Atomic_broadcast#Equivalent_to_Consensus

Your argument for "no" is flawed, for two reasons:

When we say that X reduces to Y, we mean that a solution to Y is one way to solve X.  But there might be other ways to solve X that don't rely on solving Y.
Some protocols for consensus elect a leader, but that doesn't necessarily imply that all approaches to solve consensus require electing a leader.  (For example: consider Bitcoin.  No leader, but it arguably solves a consensus kind of problem.)


I want to learn more about computer science. Where should I start? Hello computer scientists,
I am a mathematician. I have taken some undergraduate courses in C++, Python, assembly language, boolean algebra, logic, graph theory, etc.  I would like to learn more about computer science because I think it's cool. Could you give me some advice as to where to start? Thanks!

This sounds like a better fit for say academia.stackexchange, as this is mostly subjective, so bear in mind this is mostly "just my opinion".

My advice would be to start with Algorithms, at a high level: learning about the big algorithmic paradigms (greedy, dynamic, linear programming...), runtime analysis (all the landau notations and derivatives, amortised analysis...), and go through the sorting algorithms at least. A good resource for that could be [1]. This part should be seen as "fun problem solving" I reckon.
In parallel, I would study the foundations of computer science and computability (easier if you've studied Logic before):

Starting with finite automata/rational languages, and grammars
Building your way up to Turing Machines (with equivalency to recursive functions and lambda calculus)
Finally getting to the distinction between computable and undecidable

Along the way you should have got a small introduction to complexity theory, which should enable you to understand what the classes P and NP are, as well as what an NP-complete problem is.

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition (3rd. ed.). The MIT Press.


What is a proper way of solving a multibody nonlinear problem? I encountered some system of ~5000 random nodes connected by ~8000 non-hookean springs, with ~1300 nodes at the boundary fixed as the "wall", the potential of the springs are of the form $dx*e^{(dx/a)}$ where $a$ is a constant and $dx$ the strain (displacement/original length) of the spring, I am using Monte Carlo method to find the energy-minimized configuration after I performed some "perturbation", say, a simple shear or a isotropic expansion of the whole system.

It seems that the conventional energy minimization schemes such as "steepest Descent", or "simulated annealing" is not working as efficiently here as the case of linear situations, it always fail to converge to a  satisfactorily balanced state.

Could someone share your experiences in dealing with such non-linear situations?

Thank you so much!

OK, I finally fixed this issue, the right thing to do in such non-linear situation is to use simulated annealing. I am implementing a gradient guided simulated annealing, which works pretty efficiently.

Thanks for everyone who gave me suggestions and guidance to the right path!

Have fun (mixed with a lot of frustrations) with modeling!


Number of $n \times n$ binary matrices whose rows and columns sum to at most $m$ How many matrices satisfy the following constraints?

$n$ rows
$n$ columns
Cell values are either $0$ or $1$
Sum of any row is at most $m$
sum of any column is at most $m$

Is there a formula or an efficient algorithm to solve this problem?

Given $1 \leq m \leq n$, we want to determine the cardinality of the following set

$$\{ \mathrm X \in \{0,1\}^{n \times n} \mid \mathrm X 1_n \leq m 1_n \,\land\,  \mathrm 1_n^{\top} \mathrm X \leq m \mathrm 1_n^{\top} \}$$

Vectorizing, $\tilde{\mathrm x} := \mbox{vec} (\mathrm X)$, we obtain

$$\bigg\{ \tilde{\mathrm x} \in \{0,1\}^{n^2} : \begin{bmatrix} 1_n^{\top} \otimes \mathrm I_n\\ \mathrm I_n \otimes \mathrm 1_n^{\top}\end{bmatrix} \tilde{\mathrm x} \leq m \begin{bmatrix} \mathrm 1_n\\ \mathrm 1_n\end{bmatrix} \bigg\}$$

or,

$$\bigg\{ \tilde{\mathrm x} \in [0,1]^{n^2} : \begin{bmatrix} 1_n^{\top} \otimes \mathrm I_n\\ \mathrm I_n \otimes \mathrm 1_n^{\top}\end{bmatrix} \tilde{\mathrm x} \leq m \begin{bmatrix} \mathrm 1_n\\ \mathrm 1_n\end{bmatrix} \bigg\} \cap \mathbb Z^{n^2}$$

Thus, we want to count the number of integer points inside a convex polytope, or, in other words, to count the number of solutions a given integer program (IP) has. Take a look at De Loera's survey [0] and the references therein.

[0] Jesús De Loera, The Many Aspects of Counting Lattice Points in Polytopes, 2005.


Would proving P≠NP be harder than proving P=NP? Consider two possibilities for the P vs. NP problem: P=NP and P$\neq$NP.

Let Q be one of known NP-hard problems.
To prove P=NP, we need to design a single polynomial time algorithm A for Q and
prove that A correctly solves Q.

To prove P$\neq$NP, we need to show that
no polynomial time algorithm solves Q.
In other words,
we have to rule out all polynomial time algorithms.

I have heard people say this makes the second more difficult task
(assuming that it is really true).

  Is there a reason to think that proving P=NP (assuming that P=NP)
  would be easier than proving P$\neq$NP (assuming that P$\neq$NP)?

As Raphael explains, this question is ill-posed, since at most one of P=NP and P≠NP should be provable at all. However, a similar question arises in theoretical computer science in several guises, the most conspicuous of which is in the field of approximation algorithms.

Given an NP-hard optimization problem (say, maximization), we can ask how well we can approximate it. Proving an upper bound on the possible approximation is akin to P=NP, while proving a lower bound on the possible approximation is akin to P≠NP. The former is much easier than the latter. Indeed, to prove an upper bound all one has to do is to come up with an approximation algorithm and analyze it. In contrast, all known lower bounds are conditional: they are valid only if P≠NP (indeed, if P=NP then every NP-hard optimization problem would become solvable). To prove these lower bounds, we show that if we could approximate the problem too well, then we would obtain a polynomial time algorithm for some NP-hard problem. Usually this is done via the intricate technical machinery of the PCP theorem. This field, known as hardness of approximation, can be approached only be specialists, and is technical more challenging than most approximation algorithms. So in this case at least, P=NP is indeed easier than P≠NP.


Tree flattening with layout guarantees I want to flatten a binary tree into a linear array, and I wonder if there are specific algorithms to improve locality in the linearized representation (for instance, ensuring that all data from the left child of the root node appears before the data from the right child is an easy optimization.) What is the recommended approach to maintain high locality?

one solution might be Van Emde Boas layout (vEB). It is used in a hierarchical memory to optimize the number of cache misses (since it is a cache-oblivious method).

Here is how we lay a complete binary tree that has $N$ nodes in an array: split the tree in the middle (i.e. at height $h/2$ where $h= \log N + 1$). This breaks the tree into a top subtree $T_0$ of height $\lceil h/2  \rceil$ and several bottom subtrees $T_1,...,T_k$ of height $\lfloor h/2 \rfloor$, each dangling from a leaf of $T_0$.
Now store $T_0$ in the first part of array and the bottom subtrees next to it, in the order from left to right. You need to store each $T_i$ recursively, i.e. beaking into smaller subtrees until the subtrees contains only one node.

http://erikdemaine.org/papers/BRICS2002/paper.pdf


"strongly relational m-consistency when the domains contain at most m elements implies satisfiability" plain wrong? Wikipedia states

  A constraint satisfaction problem may be relationally consistent, have
  no empty domain or unsatisfiable constraint, and yet be unsatisfiable.
  There are however some cases in which this is not possible.

  The first case is that of strongly relational
  m-consistent problem when the domains contain at most m elements.

This would imply that any problem with domains of size m that is stongly m-consistent, is satisfiable. However on the same page they mention 3-colorability. It is NP-complete and consists of binary constraints on variables with domain size 3. Generally it should be possible to achieve strong-3-consistency in about $O(n^3)$, so the above statement should be wrong as it implies P=NP. What did they mean to say when the wrote the above statement? Or am I interpreting it in a wrong way?

Yes, the quoted statement is correct.  Wikipedia gives a proof in the next four sentences that immediately follow the quote you gave.

The constraints that arise from 3-colorability are not strongly relational 3-consistent, so the quoted statement implies nothing about 3-colorability.  Consequently, there is no contradiction.

(Why aren't the constraints from 3-colorability strongly relational 3-consistent?  Consider a star graph, with a vertex $v$ that is connected to three other vertices $w,x,y$.  There is one constraint per edge in the graph: e.g., one constraint that constrains the colors assigned to vertices $v,w$; one for $v,x$; and one for $v,y$.  Suppose we have a partial assignment that assigns $w$ the color red, $x$ blue, and $y$ green.  Then there is no way to assign a color to $v$ that makes the three constraints for $vw$, $vx$, and $vy$ all valid.  Thus, the constraints do not satisfy the definition of strongly relational 3-consistency.)


Unification Algorithm without Occur Check I have been reading about Unification algorithm here https://en.wikipedia.org/wiki/Unification_(computer_science)#A_unification_algorithm
. And I wonder about the importance of occur check.

I know that without occur check an unsound inference may occur. But OTOH, does the algorithm always terminate without occur check? If the two literals to unify have no variables in common I feel like the algorithm should at least always terminate right?

Say you tried to solve $f(A, g(A)) = f(B, B)$ after applying $A \to B$ you'd then have $f(A, g(A)) = f(A, A)$ and you'd have to unify $A = g(A)$ as a sub problem.


Transform inverse result let us assume that:
 f is a grayscale image of size NxN, and F is the Fourier transform of f.

G is a 2Nx2N transform obtained by inserting 0 between every value in F:

What is the inverse transform of G?

solution:
so i have programmed it, and the picture will be 4 times bigger with the picture 4 times in it. g= [f f;f f]
can you please explain why this is the answer?

Think of it the other way around.
If you duplicate an image then you get zeros in between the transform (
This can intuitively be explained:
duplicating an image is like convolving with 2 deltas (comb) of wavelength 1/2 the new image size. so is equivalent under convolution theorem to multiplying with comb of freq size of image / 2 which gives a comb with delta every other pixel -> every other pixel is zero.


Why checking if tuple belongs to join of two tables is NP-complete? I have read that checking if tuple belongs to join of two tables is NP-complete.
I had computional-complexity activities during my studies, I remember basics, however I have forgotten details. Nevertheless I don't understand why it is NP-complete, it seems to me that I can solve it in polynomial time.

Let's consider specific example:
We have two tables, $T_1$ and $T_2$, where $|T_1|=m$ and $|T_2|=n$.
Now, let $t$ will be a tuple $t=(a,b,c)$.  Then I can easily give polynomial algorithm for checking if join of $T_1$ and $T_2$ containg tuple $t$.

Is is sufficient to get $T_1\times T_2$ and in linear time check if this tuple is contained in result. Please note that size of $|T_1\times T_2|=n\times m$ is polynomial.

Where am I wrong?

If the claim is:

  for instance, given a join query $Q$ and a relational database $D$, checking if $Q(D)$ returns a tuple is NP-complete as well

the NP-completness is about the decision if that join operation returns an empty set or not (for instance because the join condition is not satisfied by any pair of tuples).

So, if this hypothesis is true, the claim is not, as you are asserting, about the fact that a certain tuple belongs to the result or not (for instance this could be checked by verifying that the tuple satisfies the join condition).


Reason for global update steps in the push-relabel algorithm I know why and how the push relabel algorithm works for solving the max-flow problem. But why is a global update step required?

Global relabeling is not required; it's an optimization. In the push-relabel paper, Goldberg and Tarjan describe a parallel version not amenable to such an update. The kind of performance problem global relabeling addresses is when two nodes u and v with surplus and residual arcs to one another become disconnected from the sink in the residual graph. The local relabeling rule can only increase u's label to one more than v's, and vice versa, so surplus is pushed back and forth and the labels slowly count up until the maximum of n is reached. Now imagine if this happens to a dense subgraph with many nodes.

By alternating m steps of push/relabel with global updates, the running time at worst goes up by a constant factor but in practice typically goes down, by a lot. The best implementations of push-relabel use gap relabeling as well as global relabeling. Both heuristics are described, with some experiments, by Cherkassky and Goldberg.


Are there noncomputable functions with a finite search space? The top rated answer to Why, really, is the Halting Problem so important? lists a few examples for a noncomputable problem. However, these mostly involve an infinite search space. Are there noncomputable problems with a finite search space? If not, why not?

Depends on what exactly you have in mind.

If the problem is to find an element with decidable (!) properties among a  recursively enumerable set $A$ (of finitely represented elements), then yes: if $A$ is finite, the problem is trivially computable. Just check every element.

If $A$ is finite but unknown, it's more interesting but still: the problem is computable, since there is an algorithm that checks the every element in $A$, even though we can't point it out. See this for an example.

If the identifying property is undecidable, then the problem may be¹ uncomputable. For instance, the search space for the question "Does TM M halt on input x?" is finite -- just two possible answers -- but the problem is (in)famously undecidable.

It's possible that the property as written down is not needed to identify the correct element.


Büchi automaton to Linear Temporal Logic Given a Büchi automaton what is the procedure to build an equivalent LTL formula? And what is its size?

I'm looking for references but I haven't found them so far.

Since Büchi automata are strictly more expressive than LTL, such a translation is not possible in the general case.

For instance, the language $L = \{w_0 w_1 w_2 \ldots \in (2^{\{a\}})^\omega \mid \exists^\infty i \in \mathbb{N}. w_{2i} = \{a\} \}$ is representable by a Büchi automaton with 3 states, but is not expressible in LTL as it is a counting language.


Proving that language $ L = \{ a^{2n}: n \geq 1\}$ is regular I was asked to prove that language described by $$ L =\{ a^{2n}: n\ge1\}$$ is regular using pumping lemma. Pumping Lemma states that for regular language we can break down language described by language into $xyz$ where pumping length $p \ge 1$ such that

$|y|>0$
$|x.y| \le p$
$x.y^{i}.z$ is in L for $i \ge 0$

taking pumping length $n = 3$ , my language becomes $L = \{ aaaaaa\}$ and then let
$$x = aaa$$
$$y = aa$$
$$z= a$$

clearly this violates condition 2 because $|xy| > p$ where $p=3$ and it also violates condition 3 for many values of $i$ thus this language cannot be regular but in the question I was asked to prove it to be regular, am I missing something?

The pumping lemma states that if a language $L$ is regular then there exists an integer $p$ such that every word $w \in L$ of length at least $p$ has a decomposition $w = xyz$ such that $|xy| \leq p$, $|y| \geq 1$, and $xy^iz \in L$ for all $i \geq 0$.

Your language satisfies the pumping lemma, with $p = 3$ (as it must, since the minimal DFA contains 3 states). Indeed, let $w \in L$ be a word of length at least 3, so that $w = a^{2n}$ for some $n \geq 2$. Then $w$ can be decomposed as follows: $w = xyz$, where $x = \epsilon$, $y = a^2$, $z = a^{2n-2}$. Note that $|xy| = 2 \leq p$, $|y| = 2 \geq 1$, and for all $i \geq 0$, $xy^iz = a^{2n-2+2i} = a^{2(n-1+i)} \in L$ since $n \geq 2$.

The pumping lemma states that every long enough word $w \in L$ has some decomposition $w = xyz$ satisfying the requirements in the lemma. It doesn't claim that all decompositions satisfy the requirements.


what is variable capture in nominal logic? While reading a paper Nominal Unification from a Higher-Order Perspective, in the abstract I noticed something feel bit confusing,

  Nominal Logic is an extension of first-order logic with equality,
    name-binding, name-swapping, and freshness of names. Contrarily to
    higher-order logic, bound variables are treated as atoms, and only free
    variables are proper unknowns in nominal unification. This allows “variable
    capture”, breaking a fundamental principle of lambda-calculus.

I know a bit about nominal logic, but as I know it respects $\alpha$-conversion, such as $\lambda x.x \approx_\alpha \lambda y.y$.
but I could not understand above statement.

I understand the notion of variable capture which leads to a wrong result during the substitution.

So does variable capture not lead to an incorrect result in nominal logic?

what does it mean saying breaking "variable capture" here?

Can anyone explain with examples?

Variable capture is the phenomenon which "breaks" things when you do your substitutions in a naive way. For example:

Correct: in the expression $$\int_0^1 (a + x)^2 dx$$ substitute $t^2$ for $a$, to get $$\int_0^1 (t^2 + x)^2 dx.$$
Correct: in the expression $$\int_0^1 (a + t)^2 dt$$ substitute $t^2$ for $a$, to get $$\int_0^1 (t^2 + u)^2 du$$ (we renamed the bound variable $t$ to $u$ on the fly to avoid capturing $t$).
Incorrect: in the expression $$\int_0^1 (a + t)^2 dt$$ substitute $t^2$ for $a$, to get $$\int_0^1 (t^2 + t)^2 dt.$$ (We ended up with a different intergral because $t$ was captured by $dt$).

Similarly, in $\lambda$-calculus:

Correct: $(\lambda x . \lambda y . y x)) y = \lambda z . z y$
Incorrect: $(\lambda x . \lambda y . y x)) y = \lambda y . y y$   (because $y$ was captured).


MSTs in Christofides Algorithm I am implementing the Christofides algorithm for TSP problem and currently I have one issue with the MST result. Let's assume that I have one graph $G$, whereas I can get $MST_1$ and $MST_2$ where both are Minimum Spanning Trees, because $G$ contains more than one edge with the same weight.

In image [2] below, the difference between $MST_1$ and $MST_2$ is basically the $Arlington \to Somerville$ or $Arlington \to Belmont$ (or vice-versa) connection. Depending on the internal representation of the graph, whether a adjacency matrix or list, this could happen by just altering which node will be the first, e.g. if $Arlington$ will be processed earlier than $Somerville$.

The difference of dealing with one or the other, is the next steps of Christofides algorithm, that requires to apply the Minimum-Weight Perfect Matching algorithm on the odd nodes.

The $MST_1$ has only $4$ odd nodes and the perfect matching result is $Arlington \to Medford$ and $Cambridge \to Everett$, which I will call $MWPF_1$.
The $MST_2$ has $6$ nodes and the perfect matching result is $Arlington \to Medford$, $Somerville \to Everett$ and $Belmont \to Cambridge$, which I will call $MWPF_2$.

The next step from Christofides is to merge both edges from $MST$ with the ones from perfect matching.

Now, if we choose to merge both $MST_1$ and $MWPF_1$, we will end up with nodes only with even degrees that's what we want as the next step is to calculate the Eulerian Circuit.

But, if we choose $MST_2$ and $MWPF_2$, we will end up with only one new edge, as other two are already present ($Somerville \to Everett$ and $Belmont \to Cambridge$) in $MST_2$.
The result then will be $4$ odd vertices and no possible Eulerian Circuit can be generated out of this merge!

How this should be dealt in Christofides algorithm? Should all the $MSTs$ generated from one graph to be tried out?

The important thing to note is that when merging the MST and the Matching, you create a multigraph. This means even when you merge, even if there are edges that already exist, you add them anyway. So you will always end up with even degree vertices.

This is step 4 of the algorithm as seen on Wikipedia.

So in your second case, you now have a multigraph where edges $(Somerville \rightarrow Everett)$ and $(Belmont \rightarrow Cambridge)$ each show up twice.


How to define a context free grammar from a regular language? I wonder how do you clasify S->a (where a is a Terminal Symbol)

It can be right linear,left linear and context free at the same time?

So the only way to distinguish them is to see what productions there are with Non-terminal symbols (like S in this example)

0) If I see S->a it can be (left/right/context-free) impossible to know

1) If I see only production in the form of S->a and S-> aS then it is right lineair

2) If I see only production in the form of S->a and S-> Sa then it is left lineair

3) If I see a mix (left and right) of the form of S-> aS and S-> Sa then I know that it is context free

4) If I see a production with a terminal symbol on the left AND on the right then I also know it is context free : like this S->aSa

Are these 5 statements correct? Am I missing scenario's to define the difference between regular and context free?

Your statement is correct. However your cases do not cover the full width of context-free grammars. All your examples are linear grammars.

In general one also allows right-hand sides that contain more than one non-terminal, like A->BC.


Dynamic data structure that checks all prefix sums of a subsequence are >= 0 and sum is = 0 Lets consider sequences whose elements are $-1,0,1$.
Subsequence $A[i...j]$ is $good$ if sum of its elements $=0$.
Example: for sequence $1,1,0,-1,-1,1$ subsequence $1,0,-1,-1,1$ is $good$.
Subsequence $A[i...j]$ is $supergood$ if it is good and every its prefix-sum is $>= 0$
Example: for sequence $1,1,0,-1,-1,1$ subsequence $1,0,-1,-1,1$ is not $supergood$ but $1,0,-1$ is $supergood$.

Now I want to have dynamic data structure which allows me efficiently do these operations:

Insert(S,x,i) - inserts $x$ into $S$ on $i$'th position
Remove(S,i) - Remove $i$'th element
isSuperGood(S, i, j) - checks if subsequence $i$, $j$ is supergood

The solution could be AVL tree with sum of elements in left and right subtree. It is easy for update and allows us to check if subsequence is good in $O(\log(n))$:

Find node i (let say v) $\ O(\log(n))$
Find node j (let say u) $\ O(\log(n))$
Check if v.val + v.lsum - u.lsum == 0 $\ O(1)$

But if it comes to checking supergood condition, I don't see how.

Augment the tree to store, for each subtree, the minimum of the prefix sums of the sequence of elements in that subtree.  Then you can check the supergood condition in $O(\log n)$ time.  It's your exercise, so I'll let you work out the details.

Hint #1: every prefix can be decomposed into a union of $O(\log n)$ subtrees.

Hint #2: the minimum of the prefix-sum of elements $[x_1,\dots,x_k]$ is the smaller of (a) the minimum of the prefix-sum of elements $[x_1,\dots,x_j]$, (b), the sum of elements $[x_1,\dots,x_j]$ plus the minimum of prefix-sum of elements $[x_{j+1},\dots,x_k]$.  Now let $[x_1,\dots,x_j]$ denote the elements in the left subtree of a node, and $[x_{j+1},\dots,x_k]$ the element in the node and the elements in the right subtree, and this gives you a way to recompute the augmented values in a node given the augmented values in its two children.

In general, the typical strategy with augmentation is that you want to choose augmented values so that (1) you can update or recompute the augmented values in a node efficiently (typically, in $O(1)$ time), given the augmented values in its two children, and (2) you can answer a query efficiently (typically, in $O(\log n)$ time), using the augmented values.  Often we handle (2) by taking advantage of the fact that every interval of consecutive values can be decomposed into a disjoint union of $O(\log n)$ subtrees.


Anomaly/outlier detection using fuzzy clustering I understand that fuzzy clustering using FCM produces a membership matrix for the set of data points we feed to it. What characteristics will an anomalous cluster produced during this method have? (Considering I only have unlabelled data)

As far as I know there is no unique definition for what is an outlier/anomaly. Therefore you'll have to decide by yourself what the characteristics of outlying data points in your data set are. This could be for example: distance to the cluster center (threshold), local neighbourhood (a data point that has no/few data points in its neighgbourhood might be an outlier) or statistical characteristics (an outlier doesn't 'fit' to the distribution of a cluster, e.g. Grubbs' method). You can find a survey of outlier detection methods in A Survey of Outlier Detection Methodologies by Hodge and Austin (2004).


What does it mean that a value can only be incremented after it's been loaded into a register? Consider the following program:

const int n = 50;
int tally;

void total() {
  int count;
  for (count = 1; count <= n; count++){
    tally++;
  }
}

void main() {
  tally = 0;
  parbegin (total (), total ());
  write (tally);
}

  Determine the proper lower bound and upper bound on the final value of the
  shared variable tally output by this concurrent program.Assume processes can execute
  at any relative speed and that a value can only be incremented after it has
  been loaded into a register by a separate machine instruction.
  Suppose that an arbitrary number of these processes are permitted to execute in
  parallel under the assumptions of part (a).What effect will this modification have
  on the range of final values of tally?

My problem is that I don't understand the question what does this mean ?

  ... and that a value can only be incremented after it has been loaded into a register by a separate machine instruction.

I feel that when two processes execute simultaneously due to this assumption some value of tally will be lost but I don't know how it can happen because I don't know what this assumption means so I can't find lower bound!it is obvious that if 2 or n process execute one after the other tally will be 100 hence 100 = (number of process *50) is upper bound!

Here are some more concepts to help with this.

CPUs use load and store instructions to execute the high level language concept of tally++;.  This is not atomic, unlike atomic CPU operations such as read-modify-write.

This question is alluding to the fact that there is no atomicity and that the common set of instructions can be executed in any interleaving by the $n$ processes.

The "lost update" concept is the enemy here. Wikipedia's "Concurrency control" article talks about this but mostly in a database transaction sense. Nevertheless it is absolutely the same high level concept of:

Thread1 reads tally into register (likely the ALU) (observes 6)
Thread2 reads tally (observes 6)
Thread1 increments ALU (now is 7)
Thread2 increments ALU (now is 7)
Thread1 writes ALU to tally memory (value stored is 7)
Thread2 writes ALU to tally memory (value stored is 7)

So BOTH threads/processes/whatever have "incremented" tally but the shared memory value of tally is ONLY 1 larger than when it started. Thread2's write to memory caused a lost update; Thread1's write was "lost".

By setting the question to say that there are at least three instructions required to increment (i.e. tally++;) the asker is saying that it is entirely possible that lost updates can occur due to interleaving of the instructions by multiple processes and causing lost updates.

I'd say the lower bound of tally is 50 (maximum destructive interleavings occur).
Upper bound is 50 * numProcesses (where no unscrupulous interleavings of the increment code occur).

Concepts to look up are:

Shared memory concurrency/parallel
Atomic and non-atomic instructions like load store and read modify write
Interleaving of instructions
Lost update


Complete $\mu$-recursive function that is not primitive recursive Could you find an example of a complete $\mu$-recursive function that is not a primitive function?

There are two standard approaches: diagonalization and rate of growth.

The definition of primitive recursive functions (whichever one you use) allows enumerating them $f_1,f_2,\ldots$. Since each primitive recursive function is total, the function $f(n) = f_n(n)+1$ is recursive. It is clearly not primitive recursive.

The other approach is exemplified by the Ackermann function, which is clearly recursive but grows too fast to be primitive recursive.