The line-covering step in the Hungarian algorithm I am trying to understand the Hungarian algorithm for the assignment problem.

I found this presentation which gives an excellent explanation about the algorithm.  However, there is one step I do not understand.

Step 3 (pages 13, 16) says "Cover all the zeros of the matrix with the
minimum number of horizontal or vertical lines".  How can this step be done in polynomial time?

I.e, given an $n\times n$ matrix with some zeros, what is an efficient algorithm for finding the smallest set of rows and/or columns that contain all the zeros?

OK, after reading this much more complicated explanation of the same algorithm, using bipartite graphs instead of matrices, I realized how to find the smallest number of rows/cols.

Given the matrix, create the "graph of zeros" - a bipartite graph where the rows are on one side and the cols are on the other side, and there is an edge between row and column iff there is a zero in their intersection. Then, our problem becomes finding a smallest vertex covering of this graph.

Based on Koenig's theorem, a smallest vertex covering in a bipartite graph can be found using any algorithm for finding a largest matching in the graph, in polynomial time.


Can You List the Names of Some Algorithms For Determining the Intersection of Two Context Free Grammars? Suppose we have two sets of strings XS and YS such that set XS is described by grammar GX and YS is described by grammar GY.

We want an algorithm which accepts GX and Gy as inputs. The algorithm will return true if the intersection of sets XS and YS is non-empty and will return false otherwise. We do not need to know exactly what the intersection is. It is possible that the intersection set is massive, so returning a container of all elements is unreasonable. Describing the intersection as a grammar is okay as long as it's apparent whether the grammar actually describes a non-empty set of string or not.

Just the name of the algorithm is fine if a Google search using that name will bring up the result. If the algorithm is obscure, additional information would be helpful.

There is no such algorithm. Start by googling undecidability. The problem itself is called "language intersection/disjointness".


Understanding sequential solution for the TAOCP 3 Million Men problem The problem and solution of interest is described here: What does > mean in this TAOCP solution?

Can anyone explain following points in that solution:

How exactly we can build (x[i], x[i+2]) for 1 <= i <= N-2 ?
What exactly means "merge G with it"? Provide exact algorithm for merging these two files.
How steps 1-4 are executed? Is it:

if (condition 1) {
    ....
}
if (condition 2) {
    ....
}
if (condition 3) {
    ....
}
if (condition 4) {
    ....
}

or

if (condition 1) {
    ....
}
else if (condition 2) {
    ....
}
else if (condition 3) {
    ....
}
else if (condition 4) {
    ....
}

?

With a for loop that steps through the array and creates a new pair from the $i$th and $(i+2)$th elements, for each $i$.
The same as the merge step in merge sort.
There are no "otherwise"s in the statement in English, so there should be no else statements.


0/1 Integer Programming and Karp's Reduction I have been reading Karp's famous paper on the NP-Completeness of different problems, Reducibility among combinatorial problems, and I have a question on the reduction from SAT to 0/1 Integer Programming defined there.

The problem 0/1 Integer Programming is defined as:
Input: Integer matrix $A$ and integer vector $d$
Property: There exists a 0/1 vector $x$ such that $Ax=b$.
Let $B$ be a boolean formula in CNF with $p$ variables $x_1,\dots, x_p$ and $n$ clauses $C_1,\dots,C_n$.
The reduction from SAT should work like this ($C_i$ is the $i^{\text{th}}$ clause of the boolean formula):
$$
a_{ij} = \begin{cases}
          1   &\text{if } x_j \in C_i \\
          -1  &\text{if } \bar{x}_j \in C_i\\
          0   &\text{otherwise}
         \end{cases}
$$
and
$$
 b_i = 1- (\text{ the number of complemented variables in } C_i ).
$$
Now if I use this procedure on the satisfiable formula
$(x_1 \vee x_2 ) \wedge (x_1 \vee x_3 ) \wedge (x_2 \vee x_3 )$, I get
$$
A =\left( \begin{array}{ccc}
1 & 1 & 0 \\
1 & 0 & 1 \\
0 & 1 & 1 \end{array} \right), \text{ and }
b = \left( \begin{array}{c}
1 \\
1 \\
1  \end{array} \right),
$$
which has no 0/1 solution. So my question is:
Have I made a very silly mistake, or is Karp's original reduction faulty?

I believe there's a typo in Karp's definition of the problem. If we replace $Ax=b$ with $Ax \geq b$, the reduction goes through as is. The easiest way I can think of to show the hardness of your problem (the one as written in Karp's paper), is via 1-in-3 SAT or via hypergraph perfect matching.


Minimum spanning tree with small set of possible edge weights Given a undirected graph which only has two different edge weights $x$ and $y$ is it possible to make a faster algorithm than Prim's algorithm or Kruskal's algorithm?

I saw on Kruskal's algorithm that it already assumes that the edges can be sorted in linear time with count sort, so then can we gain any benefit by knowing the weights of all of the edges ahead of time?

I don't think there is any benefit, but I am not sure...

No, Kruskal's algorithm doesn't make any assumptions about how fast edges can be sorted.  I suspect you misinterpreted what you read.  Kruskal's algorithm doesn't make assumptions.

You linked to a Wikipedia article.  It states:

  Provided that the edges are either already sorted or can be sorted in linear time (for example with counting sort or radix sort), the algorithm can use a more sophisticated disjoint-set data structure to run in O(E α(V)) time

"Provided" means "If", not "We assume that".

If you use a standard sorting algorithm that takes $O(E \log E)$ time, then Kruskal's algorithm runs in $O(E \log E)$ time.  If you are in a special situation where there is a way to sort the edges in linear time (e.g., using counting sort), then Kruskal's algorithm can be implemented in a way that takes $O(E \alpha(V))$ time, which is faster.  But there is no assumption that you will always be in that special situation; usually, you won't.

The case where there are only two edge weights is indeed such a special situation, and thus Kruskal's algorithm can be implemented in a way that is asymptotically faster for such graphs than for general graphs.


What is the difference between operator and function? We have operator and operands, function and formal arguments. Is the difference purely lexical (we use alphanumerics for funciton identifiers but identify operators with special characters, e.g. "+" and ">=") or it is syntactical, like I guessed here

f(a,b) -- prefix notation used for functions
a.f(b) -- infix notation for method invocation (used in OOP)
a f b  -- infix notation without dot and parenthesis used in operator invocations

so that when we write a + b we have an operator but "+"(a, b) (both ways are acceptable in VHDL) makes it a function? Do tools treat them differently? Can you differentiate them? Can you say that this is not a function, it is an operator or vice-verse? When I read the definitions in wikipedia, I do not see that syntax is a distinguishing feature of a concept. So, is it right that operators and functions are synonyms, two different words for the same thing, same meaning, same notion? I have such guess but have never seen it stated explicitly. Please agree with my guess or say what is the difference.

Historically, my guess is that the difference is rooted in how things were (and still are) translated into machine code.

An operator such as addition of integers or exclusive-or of booleans would be translated into one (or few) assembler commands which would be directly executed by the processor (resp. its ALU). It would also be part of the syntax.

A function (or procedure, method), on the other hand, is a subprogram the (main) program would explicitly jump to during execution. That is, a new stack frame is allocated, register values are saved, parameters are passed and only then is the function executed. See here for details. Furthermore, functions are defined by the programmer.

Younger programming languages have introduced more abstraction, partially or totally removing the distinction. In C#, for instance, you can overload operators for your own types. In Scala, there are no operators but only syntactic sugar for binary methods. Once these languages are compiled, though, you can see which language elements are translated to flat instructions and which to subroutine calls. Keep in mind that optimising and/or just-in-time compilers may liberally move between worlds.


What Makes an Algorthim Greedy [Graph Coloring Algorithm] I have a simple graph G = (V,E) and each vertex has a range [a,b].Every two vertices are connected only if [a_1,b_1] and [a_2,b_2] have a common subrange.
Each range of vertex is rV1 = [0,5] rV2 = [1,3] rV3 = [2,10]
rV4 = [4,9] rV5 = [6,7] rV6 = [8,12] rV7 = [11,13]
Graph Created based on above ranges.
Based on the algorithm below i have to color the graph.
ranges = rV1,rV2,rV3,rV4,rV5,rV6,rV7...

COLOR_INTERVAL_GRAPH(rV1,rV2,rV3,rV4,rV5,rV6,rV7...){
if(number of rVi > 0){
 C_m  = MAXIMAL_COLOR_CLASS(rV1,rV2,rV3,rV4,rV5,rV6,rV7...);
 //paint C_m vertices with color m.
 //new_ranges <- remove C_m from rV1,rV2,rV3,rV4,rV5,rV6,rV7...
 return {C_m} U COLOR_INTERVAL_GRAPH(new_ranges)
 else:
   return []

MAXIMAL_COLOR_CLASS(new_range){
C = []
i = 1
while(i <= new_range.size()){
  C = C U {Vi}
  j = i+1
  while(j <= new_range.size() AND rVi (not common subrange with rVj)){
  j = j+1
i=j
return C

How i know if the above algorithm uses the greedy strategy?
My work so far:
The algorithm has the 'greedy choice property' since it paints the most each turn, by choosing the best solution to the current subproblem without caring about future problems or backtracking.(can this be improved and how)?
Graph Colored (Is the graph colored correctly?).

"A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage." (from Wikipedia)  In other words, it does not backtrack.  It builds up the solution incrementally, and when it adds something to the solution-so-far, it never later removes it (or, when it makes a decision, it never later undoes that decision).
Does that describe the algorithm you are looking at?
If you want to justify that it satisfies the greedy choice property, it might help to precisely state what is the "subproblem" that is solved at each step.


Thought process for the following problem? We are given a 1-d array and we have to return  the smallest array attainable after removing all the continuous same numbers. We can only eliminate those numbers which repeat continuously more than or equal to 3 times.

So for eg. [1, 3, 3, 3, 2, 2, 2, 3, 1] should return [1, 1] i.e. first the elimination of 2's occuring three times and after its elimination there is 3 for four times at stretch. After eliminating 3's we are left with 1's which occur less than three times, so no elimination.

Similarly [3,1,2,2,2,1,1,1,2,2,3,1,1,2,2,2,1,1,1,2,3] should return [3,1,3,2,3]. Here we can jumble the eliminations in different ways but no order of eliminations can lead to an array less than in size than [3,1,3,2,3].

The time complexity should have a tighter upper bound than $O(n^2)$.

I am thinking of this problem but I haven't been able to identify a specific technique for solving it. I am thinking of hashing, graphs and also recursion but till now I have failure tackling the order of eliminations as the eliminations can happen in random order. More than the solution I would like to know the technique and thought process walkthrough of this problem.

Using O(n) extra space, you need to record start for each run of same numbers. Scan the array linearly. Once you removed a run, you either continue previous run, or start a new one.

for i:
  if a[i] != a[i-1]:
    if run[x] - run[x-1] >= 3:
      x--
      // avoid copying the run into output array
    if a[run[x]] != a[i]:
      x++
    run[x] = i

On the second thought, you don't need the run[] array - only start the of current run. Once a run eliminated, you can check that previous run is at least 3 elements long in O(1) operations. You still need O(n) place to store the list of eliminated ranges, though.


context free grammar for palindrome: $L_n = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$ Let $L_{n} = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$

Generate a cfg of $L_n$

For n = 1, 2, 3

Informally, x is in $L_n$ means
    some palindrome of at least length n is a substring of x that occurs
    exactly at the midpoint of x.

for $n = 1$

$S \to 0S0 | 1S1 | 0S1 | 1S0|0 | 1 | 00 | 11$

for $n = 2$

$S \to 0S0 | 1S1 | 0S1 | 1S0 | 0A0 | 1A1$

$A \to 0 | 1 | \epsilon$

for $n = 3$

$S \to 0S0 | 1S1 | 0S1 | 1S0 | 0A0 | 1A1$

$A \to 0 | 1 | 00 | 11 | \epsilon$

would this be right?

Say I changed it to $|y| > |z|$ or $|y| < |z|$ how would this differ?

When $n=1$, the language $L_1$ consists of all words of the form $ywz$, where $|y|=|z|$ and $w$ is a non-empty palindrome. We can generate all non-empty palindromes as follows:
$$
P \to 0P0 \mid 1P1 \mid 0 \mid 1 \mid 00 \mid 11
$$
Given that, we can generate $L_1$ by capturing also the outer part:
$$
S \to 0S0 \mid 0S1 \mid 1S0 \mid 1S1 \mid P
$$
For larger $n$, all we need to change is the "base cases" for $P$.

Further observation reveals that we can actually assume that $|w| \leq 2$ (for $n = 1$), and so we can use alternatively the following productions for $P$:
$$
P \to 0 \mid 1 \mid 00 \mid 11
$$
This allows us to eliminate $P$ from the grammar, reaching the following grammar:
$$
S \to 0S0 \mid 0S1 \mid 1S0 \mid 1S1 \mid 0 \mid 1 \mid 00 \mid 11
$$
These steps can also be extended to larger $n$.


Trie traversal to maximise XOR in a tree but with a condition Input:I am provided with x and y.

x is a 32 bit non negative integer and y is some node-id of the tree.

So, I built a trie with 32-bit non negative integer values which are the keys associated with each node-id of the tree (DAG). Now, if I am asked to find the a node, whose key XOR x is maximum. This can be easily be done in O(log n) just by traversing the trie.

Now here is the extra condition:

I want to find the key on the node in the path from root to that node y, for which x XOR (key) is maximum.
How can we find this out efficiently? Preferably in O(log n).

You can simply use persistent tries.

Let $T[x]$ denote a trie containing all keys in the path from root to $x$, assume $y$ is a child of $x$, $T[y]$ can be constructed in $O(\log U)$ time from $T[x]$, where $U=2^{32}$. This is trivial even if you use normal tries; but the key point is "persistent" data structures enable you to store all $T[\cdot]$ at the same time. As an intuition, notice that when we construct $T[y]$ from $T[x]$, only $O(\log U)$ nodes in $T[x]$ changes.


Complexity of a subset sum variant Is this variant of the subset sum problem easy/known?

Given an integer $m$, and a set of positive integers $A = \{x_1, x_2, ..., x_n\}$ such that every $x_i$ has at most $k=2$ bits set to $1$ ($x_i = 2^{b_{i_1}}+2^{b_{i_2}},\;\; b_{i_1},b_{i_2}\geq 0$); is there a subset $A' \subseteq A$ such that the sum of its elements is equal to $m$ ?

Is it in $\sf{P}$? Is it still $\sf{NP}$-complete?

And if every $x_i$ has at most $k=3$ bits set to $1$? For $k=1$ the problem is trivial.

It is still $\sf{NP}$-complete, even for $k=2$. Given an instance of subset sum, we can transform it in to this variant by splitting up the numbers and adding some extra bits.

First, the sum of all numbers in the problem will be less than $2^m$ for some value of $m$.

Now, let's take a number $n$ from the original problem which has $k$ bits set. We will split this number in to $k$ numbers with exactly 2 bits set such that the sum of those numbers is $n+2^{k+m}$. We can do this recursively, by finding $\lceil{k}\rceil$ numbers that sum up to the first $\lceil{k}\rceil$ bits plus $2^{k+m-1}$ and $\lfloor{k}\rfloor$ numbers that sum up to the last $\lfloor{k}\rfloor$ bits plus $2^{k+m-1}$.

In addition to that number we will also add the number $2^{k+m}$ to the problem. A solution must either contain this number or all of the $k$ numbers constructed previously. If the original target value was $t$ the new target value will be $t+2^{k+m}$.

If the original problem had more than one number, we can repeat this process taking $k+m+1$ for the new value of $m$.

There are only two ways the bit at position $k+m$ can be set: the answer can contain the number $2^{k+m}$ or all of the $k$ numbers that sum up to $n+2^{k+m}$. So we have reduced subset sum to your subset sum variant.

As an example, let's take ${\{2,3,5\}}$ with target value $7$. This problem could be encoded as the subset sum variant presented here by taking the following binary numbers:

2 gets mapped to $0100\ 1$ and $0000\ 1$. (Using the extra bit is not strictly necessary here.)

3 gets mapped to $1000\ 00\ 1, 0100\ 00\ 1$ and $0000\ 00\ 01$

5 gets mapped to $1000\ 00\ 000\ 1, 0010\ 00\ 000\ 1$ and $0000\ 00\ 000\ 01$.

The new target value would become $1110\ 10\ 010\ 01$.

If the original problem is represented with $n$ bits, then the transformed problem has at most $O(n^4)$ bits. The original problem will have at most $O(n)$ numbers each with at most $O(n)$ bits, so the sum of all of them is also O(n). The transformed problem will have $O(n^2)$ numbers (since each $n$-bit number is split in to $n+1$ $2$-bit numbers, with their length being at most $O(n^2)$ since we use $n$ additional bits for each number. So the total size of the transformed problem is $O(n^4)$ bits.


What is the difference between python list and c++ vector? I read about the similarities between the python list and c++ vector and it looks as if the only difference is python list is heterogeneous. Are there any other differences? How are they both implemented?

Both python list and c++ vector are implemented as dynamic arrays (https://en.wikipedia.org/wiki/Dynamic_array).
(Essentially arrays that get reallocated when they are too small.)
Now the important difference between the python and c++ version don't come from the data structures themselves, but rather from the language. In c++ you can store structs, primitive data types pointers etc. in a vector. But in python everything is a pointer in the sense that an e.g. an integer is stored in the heap and it has an annotation attached to it that says "i am an integer". That's required because python has a dynamic type system. And the elements stored in the list are only pointers to the actual elements. This mechanism also allows python to store different data types in the same list. This is another reason why python is kinda slow.


Checking membership in DFA with fixed length using AC1 circuit? I'm supposed to find circuits , which can solve the question of membership in a regular language A with fixed length. The depth is limited by O(log(n)) and the size by O(n).  Divide and Conquer should be the way to go, but I always exceed the max size. Would really appreciate any help

Let $T$ by a balanced binary tree with $n$ leaves, and label each internal node $v$ by the interval $I_v$ consisting of the leaves below $v$. For each $v$ we will calculate the a two-place relation $R_v(s,t)$ which checks whether $I_v$ causes the automaton to move from $s$ to $t$. If $a,b$ are the two children of $v$, then
$$
R_v(s,t) = \bigvee_u (R_a(s,u) \land R_b(u,t)).
$$
For a leaf $f$, $R_f(s,t) = [\delta(s,x_f) = t]$, where $x_f$ is the $f$th input, and $\delta$ is the transition function. If $r$ is the root of the tree then the final answer is
$$
\bigvee_{q \in F} R_r(q_0,q),
$$
where $q_0$ is the initial state and $F$ is the set of accepting states.

Each node of the tree uses $O(1)$ gates. Since the tree has $O(n)$ nodes, the circuit has size $O(n)$. It's also not difficult to check that it has depth $O(\log n)$. Moreover, the fan-in of each gate is constant (since the number of states is constant), and so this circuit is actually in $\mathsf{NC}^1$.

Note also that the construction works directly for NFAs.


Sort half-edges around common vertex in 3d I'm trying to figure out this problem for very long time and am no getting nowhere. I'm working on a simple 3d modeler that uses half-edge data structure.
Say I have non-manifold geometry where two triangles share a common vertex, as shown in the image below. And I want to add another triangle such that now three triangles share a common vertex. Once we add the new triangle we need to reorder the half-edges around the common vertex. In 2d this ordering is done by sorting the half-edges from the common vertex clockwise, as explained in this post.
However in 3d this becomes a nightmare. If the same three triangles share the common vertex but have an arbitrary orientation in 3d space and are not coplanar. How can one possibly sort the half-edges?
I experimented with using the common vertex normal to construct a plane, and project all the half-edges around the vertex to that plane. After which we could sort them clockwise relative to the plane. But I've found this approach to have a lot of issues. And now I'm all out of ideas.

It seems that the problem here is that you try to determine something similar to a rotation system from a skeleton1 embedded in $\mathbb{R}^3$. The problem here is that such a skeleton is not enough to uniquely define a rotation system, because rotation systems encode embeddings of a graph onto a surface. Without having access to a given surface as a reference, almost any rotation along a vertex is possible, and you will not be able to find the "right" one.
So what can you do? This likely depends a bit on what it is you are actually modelling. Since the rotation around a vertex is a concept that depends on a surface, to determine it you will have to decide what your surface looks like, at least locally around the vertex you're inserting a triangle in. Likely, the edges that are part of a triangle should always be consecutive in the ordering, but that doesn't give all the information.
One possible approach on how to decide where a new triangle fits into the ordering, is to look at all consecutive pairs of triangles in the existing ordering, and insert the new triangle in between the pair with smallest distance to the new triangle. (Note that you have to store the ordering around the vertex explicitly, you cannot compute this on the fly)
More precisely, to determine where to place a new triangle incident to vertex $v$ in the ordering around $v$, consider all pairs of consecutive edges $(e_i,e_{i+1})$ that do not form a triangle with vertices $(a,b)$ being their endpoints not equal to $v$. Let $(x,y)$ be the new vertices of the triangle. Place the edges of the new triangle in between the pair of edges $(e_i,e_{i+1})$ such that $\min(\|a-x\|+\|b-y\|, \|a-y\|+\|b-x\|)$ (or another similarity measure of the pairs $(x,y)$ and $(a,b)$) is minimized.
For example, in the figure below, vertices with the same colors are the pairs we'd compare with our new vertices $x,y$.

1: I will assume that you just have a graph for now, but perhaps a simplicial complex might be a better description? I don't think it matters much for the discussion here, though.


Dominator Tree for DAG Is there a fast algorithm to compute dominator tree for acyclic graphs?

The Lengauer-Tarjan Algorithm is a fast algorithm for general flowgraphs. But if a graph is acyclic, do we have a faster algorithm?

Recall the definition of dominators:

$$\hbox{Dom}(n_o) = \{ n_o \}$$
$$\hbox{Dom}(n) = \{ n \} \cup \bigcap_{p \in \hbox{preds}(n)} \hbox{Dom}(p)$$

This can be done in a single pass over all nodes, if you can guarantee that you visit all predecessors of a node before you visit that node. So perform a topological sort, and you're done.

It may be possible to calculate dominator trees directly (i.e. without first computing dominators) if the graph is a DAG, but I'm not certain how you would do this.


Can I use the following method to prove an algorithm is correct? I'm trying to show that a solution I have obtained via an algorithm is correct. The way I plan on doing this is first by showing that an optimal solution does indeed exist. Then, I plan on showing that every other solution that is not the solution provided by my algorithm cannot be optimal. Finally, I show that the solution I have cannot be improved in the same way as any other solution.

Is this enough to show that my algorithm is optimal? In this case I am avoiding doing an "exchange argument" a la greedy algorithms. In fact, I don't really prove anything about how my solution is an improvement of the other ones, but simply that all of the other ones can be improved, and given that an optimal solution exists, the one I have must be it because it cannot be improved in the same way that the other ones can.

I am rather surprised that you raised this question since the meticulous and enlightening answers you have written to some math questions demonstrate sufficiently that you are capable of rigorous logical deduction. It seems that you became somewhat uncomfortable when you stumbled upon a new and unorthodox way to prove an algorithm is correct.

Believe in yourself. Believe in logic.

Yes, I believe you have shown your algorithm is correct. To be absolutely clear, suppose you have shown all of the following.

An optimal solution exists.
Your algorithm provides a solution and only one solution.
Every solution that is not the solution provided by your algorithm cannot be optimal.

Then your algorithm must provide an optimal solution. The implication is just simple logic.

You do not even need to show that solution provided cannot be improved in the same way as any other solution.


Help with question from Sipser chapter 1 Is this language regular?

$0^k10^k \ with \ k\geq1$

It needs to count the starting and ending zeros which is impossible with finite states.

Update:
This is the whole problem from the book:

Let $\sum = \{0,1\}$.
Let $A =\{0^ku0^k  \ | \ k \ge 1 \ and \ u \in \sum^*$}.
Show that $A$ is regular.

My reasoning is that $u$ can be $\{0,00,000,...,01,011,...,1,11,111,11111...etc\}$

So, the language $0^k10^k \ with \ k\geq1$ should be regular.

I don´t want a formal proof of the problem, but to check if my reasoning is correct.
Thanks.

I think I finally understood the concept.

This:

$A =\{0^ku0^k  \ | \ k \ge 1 \ and \ u \in \sum^*$}.

Means that A has strings that starts and ends with the same number of zeros.

For example, the string:

$0000000100$

Is recognized by A because:

$00|000001|00$

In the middle we can put any number of zeros and shrink the zeros at the edges.

$0^k10^k$ is another language that contains strings with equal number of zeros at the beginning and end separated by a 1. In this case, string from this language are accepted by the the first one but that doesn't means that the second language could be regular.


Is Green's the best 16-input sorting network so far? Every paper says that Green's construction is the best 16-input sorting
network as for now.

But why does Wikipedia says: "Size, lower bound: 53"?

I thought "lower bound" meant:"If there exists at least an algorithm that can...". Am I wrong?

No, a lower bound means that somebody has proved that anything smaller than 53 is impossible. That doesn't mean that a 53-gate network is known or even necessarily possible; just that there cannot be a smaller one than that.


Removing constant symbols from language to prove irregularity I'm confused about a solution I saw about the following language not being regular:\begin{equation*}
  L=\{0^n ~1 ~2^n : n >0\}
\end{equation*} The example solution said that $L$ was "the same as":\begin{equation*}
 L'=\{0^n1^n : n > 0 \}
\end{equation*} so it wasn't regular. I understand why $L'$ isn't regular, but I don't understand how $L$ is the same as $L'$. How can you eliminate that middle symbol?

The language $L'$ is the "same" as $L$ (in fact, it's an asymmetric relation) in two steps. If $L$ were regular, then so would be $L'' = \{0^n 2^n : n > 0 \}$ (take a DFA for $L$ and replace $1$ edges with $\epsilon$ edges). In its turn, $L''$ is the same as $L'$, up to change of symbols.


Generating all factorials up to $n$: faster than naive approach? I'm aware of prime decomposition and parallel approaches to calculating one factorial; however, if I want the factorials of all numbers up to $n$, is there anything more efficient than the naive approach? As far as I can tell, at least the prime decomposition algorithms aren't any more useful here than the naive approach. Karatsuba multiplication may be useful, but that's something that would have to be dealt with in the data structure that handles arbitrarily large integers, if I'm not mistaken.


How to decide if CSP is ambiguous? When you pick up some reading about CSP the main focus is how to solve it. My goal is to compute/decide if CSP is ambiguous (has 2 or more solutions) or not (has 1 solution).

Of course brute-force approach would be to solve it and see the outcome. But I am looking for something simpler (read: way faster).

Background: I would like to write Zebra puzzle generator. There is no much resources about it, as with regular CSP, most are solvers, and 2 links I followed take such approach -- start from all clues, at each step reduce by one and solve it. If it unsolvable, get back that clue, and continue.

You shouldn't be able to beat the complexity of brute-forcing (because of having to check all possible assignments in the case that the CSP is not satisfiable). Instead, I offer the possibility of smart brute-forcing:

Solve the CSP normally and find a single assignment that satisfies it, if one exists. Add the negation of that assignment as a new constraint and jump back to the immediate last decision assignment you made and continue from there. This is a typical procedure for SAT solvers which traverse Implication Graphs and add conflicting clauses as constraints before backtracking to the last assignment decision. However, in the case of solving a SAT problem, each boolean variable can only have one of two possible assignments which is not true for the domains of constraints of CSPs, so you might actually need to backtrack further to find another complete assignment of all variables if one should exist (as per usual brute-forcing).

Let's suppose you have a CSP of three variables $A, B, C$. If you find a solution to the CSP whereby (let's say) C was assigned last, you could backtrack to the point right before making the assignment to C and continue from there, seeing if the same assignments of $A$ and $B$ could lead to a second solution with a different assignment of $C$. After finding your second solution, you could immediately terminate, knowing that the CSP is ambiguous. However, you might have to very well check all possible assignments of each variable in the case your initial solution to the CSP were the only solution (or even when your CSP is not satisfiable), in which case it would be unambiguous. So clearly, this procedure would only improve your efficiency for ambiguous CSPs where any two of all solutions differ with a single variable assignment.


Algorithm for optimal rule-based arrangements? I am trying to plant a row in a garden. Certain plants are good for some plants and bad for others, and I am trying to find the best order of plants: most adjacent friends and no adjacent foes, as defined in this table(I have one of each):

Num Vegetable     Friends      Foes
1   Watermelon    7,4,3        8,6
2   Tomatoes      9,8,6,5,1    7
3   Sunflowers    7,6,11
4   Zucchini      9,7,3
5   Eggplant      9,6,2        7,10
6   Cucumbers     9,7,3        8,1
7   Corn          8,6,4,3,1    5,2
8   Cantaloup     7,4,3        6,1
9   Bell peppers  6,5,11,10,2
10  Swiss chard   2            5
11  Rhubarb       9,3

How do I find the arrangement? Sort them using an algorithm? The title was my best guess at the answer. I am trying to understand the thought process and the implementation.

As @Steven wrote, this problem is NP-hard. However that doesn't mean that you can't solve the problem for small instances.

You can solve such a problem by simply iterating over all $n!$ different permutations, and checking each if any of the arrangements is allowed and how good it is. This has complexity $O(n \cdot n!)$.

Much faster (but still exponential complexity) will be a variation to the Bellman–Held–Karp algorithm. Compute for each pair $(V, v)$ with $V$ being a subset of all vegetables and and $v \in V$, if it is possible to arrange the vegetables $V$ in a way such that $v$ is the last one and what it's best value is. You can define a recursive formula for this function, and apply dynamic programming, like in the BHK algorithm. That should run in $O(n^2 \cdot 2^n)$.


How to construct a Turing machine for a language I have proved that language $L$ is not regular and think that it is recognizable by a Turing machine. I want to prove it by constructing a Turing machine for it.

$L=\{0^n|n \in A\}$
where $A$ is set of all numbers that do not contain 1 in their base 3 representation. However, n is in base 10.

What I have done so far:
When I was proving that the language is not regular, I used the fact that there cannot be any arithmetic sequences in $A$. I think if I work on the number of 1 in base three, I may get somewhere.

Try to come up with an algorithm, and then write the simplest possible program in some usual programming language for recognizing L. Then translate that program to a Turing machine.

N is not "in base 10" - it's just a number in your computer's memory, which is probably internally represented in base 2, but your program shouldn't care.

To check if a number contains 1 in base 3 representation, try to build the base-3 representation using the usual base conversion algorithm (digit = x mod 3, proceed with x div 3), and stop when you see a 1.


How do computers *really* work? (at the most basic level) While learning about computers I will read about RAM and Storage and the CPU, and while these explain the architecture of a computer and how parts of a computer work together, I still don't understand the fundamental workings of a computer program.
Let me take an example.
I'm on the web on a mac right now. When I push two fingers away from me on the trackpad, I understand that the trackpad is made up of a capacitive touch screen that, when your finger is placed on it, draws current and the trackpad detects that and converts it into data that explains the movement of my fingers up the screen.
However, when you have this data in binary form, or machine code, it goes through logic gates and other things to make it in scroll down on the page. But what is actually happening here? How would the computer have physical things that operate differently based on the input? What operations are carried out on the machine code that says "if data looks like 01001010 10101010... send instruction 10010010... to CPU that tells computer to scroll down". Surely if you had some logic gates that turned input x into output y, yes they would give different outputs based on the input, but unless you somehow redirected the current to the right set of logic gates every time the action was carried out, how would it go to the correct one? To me this step is still magic. Especially with computers now that have no moving parts it seems even more alien.
Could someone explain this to me?

This is a complex matter. To begin with, when you move your mouse, there is so much going on at once, that I cannot even begin to explain everything here. So, I will focus on the most fundamental thing: How does the computer actually compute?
As you are probably familiar with, computers have memory called RAM, and a CPU that is able to execute "commands". Commands, are essentially some form of data, that allows the computer to decide which logic gates to pass the input to.
At its core, this is the work of the ALU in the CPU. ALU stands for Arithmetic Logic Unit, and it had three inputs, contrary to what you may think. The first two inputs are normal inputs for the operations, for example: two numbers $a,b$ that we want to sum up. The third input, decides what operation to do on them. For example, you can encode that "0001" means we want to sum the two numbers, while "0010" might mean multiplication and "0011" is division. This ALU does this magic!
This "magic" that decides based on the third input which operation to do, is done via applying a multiplexer circuit to take the output from the correct series of logic gates in the ALU.
Basically, an $n$-to-$1$ multiplexer is given $n$ "normal" inputs, and one "special" input that decides which of the $n$ inputs to output. Yes, it simply outputs one of its inputs without changing anything. Basically, if we think of its inputs as an list $inp$, and the "special" input is called $s$, then the output is $inp[s]$.
The ALU takes this, and gives to it as the $inp$ the list of all possible operations on the two numbers $a,b$, and thats how the ALU knows which operation to apply when.


Unique SAT complexity clarification Unique SAT is defined as:

Given any SAT problem, does the SAT problem have exactly 1 solution?

As I understand it is co-NPHard. I am unclear how it is in co-NP

Assuming the problem has more than 1 solution, any 2 solutions can be a certificate of it being nonUnique. That part is coNP. Now, given a problem can be unsatisfiable, how do we get a certificate of no solution?
Its also said that an NP Oracle can solve this problem in polynomial time, but an NP Oracle just tells if the problem is satisfiable. So how is that possible?

Apologies but I have no clue regarding this version of SAT.

To prove coNP-hardness, you don't need a certificate (that would be needed only if you wanted to show coNP-completeness). We just need some coNP-hard problem that reduces to UniqueSAT. UniqueSAT is indeed likely not in coNP.
You can ask an oracle multiple queries. You could begin by asking if the formula has a satisfying assignment (and, using self-reduction, find a solution if one exists). Perhaps you can then use further queries to determine if another solution exists?


Is the minimum bottleneck spanning tree also a minimum spanning tree for an undirected graph with unique edge weights? I can see a counterexample such as this:

But I can also see in some cases it could be the same. I am trying to understand what property makes a MBST also a MST?

Let $G = (V,E)$ be the input graph. And, let $G_{M} = (V,E_{M})$ be an MST of this graph. First, note the following properties of the MST and BMST.

An MST is always a BMST

If all edges in the graph have distinct edge weights, there is always a unique MST.

Let $e$ be any edge in $E_{M}$. Let $(S_{e},V \setminus S_{e})$ be the cut obtained after removing $e$ from the graph $G_{M}$ and $C_{e}$ denote the edges of $G$ that goes across this cut. Then, $e$ is the minimum weight edge among the edges in $C_{e}$.

Following is the property that is required for a BMST to be an MST.

Property: Every BMST is an MST if and only if for every $e \in E_M{}$, all edges in $C_{e} \setminus \{e\}$ have weight greater than $w$, where $w$ denote the weight of the bottleneck edge in a BMST or MST.

Proof:  First, let us prove the 'only if' direction.
($\to$) Suppose every BMST is an MST. For the sake of contradiction assume that there is an edge $e \in E_{M}$ such that there exist an edge $e'$ in $C_{e} \setminus \{e\}$ that has weight smaller than $w$. Let us remove $e$ from $G_{M}$ and add $e'$ to $G_{M}$. Let this new graph is $G_{M}'$. It is easy to see that this graph is a BMST. However, it is not an MST since
$$\begin{align} Total\_Weight(G_{M'}) &= Total\_Weight(G_{M}) - w(e) + w(e')\\ &> Total\_Weight(G_{M}) \end{align}$$
Here, I have used the fact that $w(e) < w(e')$ by Property 3 of MST.
This contradicts the fact that every BMST is an
MST. This completes the proof of the 'only if' direction. Now, let us prove the 'if' direction.
($\gets$) Suppose for every $e \in E_{M}$, all edges in $C_{e} \setminus \{e\}$ have weight greater than $w$. For the sake of contradiction, assume that there is a BMST $G_{B} = (V_{B},E_{B})$ that is not an MST. Therefore, we can say that there is an edge $e$ in $E_{M}$ that is not in $E_{B}$. Now, remove this edge form the graph $G_{M}$ and let $(S_{e}, V \setminus S_{e})$ be the corresponding cut. Let $u$ be a vertex in $S_{e}$, and $v$ be a vertex in $V \setminus S_{e}$. Let $p$ be a path from $u$ to $v$ in $G_{B}$. It means, there exist an edge $e' \in p$ that goes across the cut. In other words, $e'$ belongs to $C_{e}$. Now, note that since $e' \in G_{B}$, the weight of $e'$ is $\leq$ $w$. It contradicts the fact that all edges in $C_{e} \setminus \{e\}$ have weight greater than $w$. This prove the 'if' direction. Hence the proof is complete.


Best starter resources for learning about AI I want to start learning of AI and have an idea to program "social evolution simulator" but want to hear any advice to avoid creation "well known bicycles" and get strong knowledge-base. Will be grateful for online resources and/or books. Thanks.

Also, I understand, that any programming language can be used for this, but probably some language is already more suitable for.

Artificial intelligence is vast.

A seminal paper by Marvin Minsky (1963) will be best place to start. I consider it to be a fundamental resource. Minsky wrote this paper in 1963, and set the foundations of much of the modern terminology of AI.

Minsky, Marvin. "Steps toward artificial intelligence." Proceedings of the IRE 49.1 (1961): 8-30.

Books

"Artificial Intelligence: A Modern Approach" by Russell and Norvig
Overview of constraint programming "Principles of Constraint
Programming by Krzysztof Apt".
Advanced book "Foundations of Statistical Natural Language Processing
by Christopher D. Manning and Hinrich Schuetze".
Machine learning methods  "Machine Learning by Tom M. Mitchell".
Intelligence by Jeff Hawkins and How to Create a Mind by Ray Kurzweil
The Emotion Machine by Marvin Minsky
Artificial Intelligence: A Modern Approach by Peter Norvig and Stuart
J. Russell
Artifical Intelligence - A Modern Approach by Russell and Norvig
Sciences of the Artifical by Herb Simon
"INTRODUCTION TO MACHINE LEARNING" from Nils J. Nilson
"An Introduction to Neural Networks" from Ben Krose and Patrick
van der Smagt
"Information Theory, Inference, and Learning Algorithms" part V, from
David J.C. MacKay

Online material

Recommend blog The AI Revolution: Road to Superintelligence - Wait
But Why
Coursera
Udacity
20 free books to get started with Artificial Intelligence
The AI Programmer's Bookshelf
Artificial Intelligence: Foundations of Computational Agents
Deep Learning

Language (my prioritizes)

Python
Java

Open Source Software Library

Google's TensorFlow
Theano
Microsoft's CNTK
Facebook's Torch
DL4J
Caffe


Is this a kind of "sketching"? Say one is given a matrix (assume real and symmetric if necessary) and its $n-$dimensional columns be say $v_1,v_2,..,v_n$. Now is it possible to find a set of $d<n$ lower dimensional vectors ($w_1,..,w_d$) such that they form a $d \times d$ matrix $B$ (assume real and symmetric) with either of these properties,

That the $d$ eigenvalues of $B$ are "close" to the top$-d$ eigenvalues of $A$? (and hence the correspomding eigenvectors are also "close" in some sense?)
That the spectral norm of $B$ is "close" to the spectral norm of $A$.

Will this be called "sketching"?
Does Johnson-Lindenenstrauss lemma help in doing these?

Yes, you can match the eigenvalues.  It is easy to construct a matrix with any desired eigenvalues: for instance, create a diagonal matrix and put the desired values on the diagonal.  Thus, you can get an exact match, not just an approximate match.  Nothing fancy is needed.

No, matching the eigenvalues doesn't imply that the eigenvectors of $B$ are somehow related in any way to the eigenvectors of $A$.

Given a value $n$ you can easily construct a matrix $B$ whose spectral norm is $n$, so that too can be exactly matched.

You don't need the Johnson–Lindenstrauss lemma for these results.


Can you form a group with assembly instructions under the MIPS-32 architecture? Would it be possible to form such a group using the ADD instruction and the NOT instruction?

Sure.  The integers modulo $2^{32}$ form a group.  The group operation is addition modulo $2^{32}$, which can be implemented by the ADD instruction.  You don't need the NOT instruction.

There are other groups you could form, such as the integers modulo 2, and many more.  I recommend you read the definition of a group and play around with some examples.


Could the halting problem in theory be solved for any finite set of Turing Machines? Suppose there's a program A that decides whether or not every program halts.
Then we could construct program B that invokes A and does the opposite. Do I halt? If so, loop. Do I loop? If so halt.
That shows we cannot construct program B.
HOWEVER, that assumes B can be embedded in A.
Could there exist a program B that decides all programs of length N or less - their halting, such that B is greater in length than N?
In other words, the "halter decider" is necessarily bigger than the programs it's proving.
Trivially, there exists a computer program that decides the halting of all programs of length 100 or less. There's 2^100 programs of length 100 or less (assuming programs are encoded in base-2). Therefore there's a base-2 number with length 2^100 where each bit corresponds to whether or not the program halts.
Thus, you can solve the halting problem for any arbitrary length or less.
In general, given a finite set M of Turing Machines, there exists a Turing Machine that decides the halting problem for M
Anything wrong with this logic?

Your logic is somewhat correct. I will start by discussing the new definition you tried to give for the halting problem, and then move on to explain the finite set of TMs.

Halting problem, with size less than the TM that solves it
This idea is certainly interesting, but it has some inherent problems with it.
First is a syntax problem. What language is here? Since $N$ is not bounded, this cannot be expressed as a usual computational problem with TMs. In order to formalize this you might want to create a new definition.
The second problem, is a bit more subtle: How do you define the "size" of a TM?
For example, if you decide to define it as the running time of the algorithm, then obviously is such a $B$ for every $N$ (just do a loop that does nothing for $N-1$ steps and after that accept). But if you define it as the length of the code plus the length of the inputs, then you can show that there is no such $B$ for big enough $N$. (the formal halting problem gets two inputs $A,X$ where $A$ is a program code and $X$ is some string, and you create a new TM that simulates it with only one input instead of two, reducing the size)
Those examples are obviously two opposite sides of a wide spectrum. You want to formally define the problem and the definition of the size of a TM before you can think of whether or not its possible.

Finite set of TM
The formalization of the halting problem $H$ is as follows: $H=\{\langle M, x \rangle : M \text{ is a TM }\land M(x)\text{ halts}\}$
With this definition, even if you restrict it so $M$ would be in a predefined finite set of TMs, and even if this set contains only one TM, this is an undecidable problem! The counterexample, is $U$ - the universal TM. We will use a slightly different version of it, since we dont need its full power. $U$ (in this context) gets one input, which is a string representing a TM, and $U$ simulates this TM with the input $\epsilon$. Then solving whether $U$ halts on some input or not, is undecidable, since its equivalent to the problem called $H_\epsilon$ which is known to be undecidable.
However, if you would restrict the $H_\epsilon$ problem itself for only a finite set of TMs, the problem becomes decidable, and even more! It becomes a regular language. This is because for each $TM$ in this finite set we know beforehand whether or not it halts, and we dont have to actually do any computation apart from assigning each of those $TM$ the correct label we already know.


Are fixed-point combinators general recursive? I don't know if I'm using the vocabulary correctly, but what I'm interested in is this: If your language has fixed-point combinators, is it Turing-complete?

Yes, fixed point combinators are sufficient for general recursion and Turing complete computations.

In my Awelon project languages, fixed point combinators are the only way to model recursion. In practice, working directly with fixed point is rather annoying. However, it isn't difficult to build more conventional loop primitives (while, until, repeat) and collections-oriented abstractions (fold, map, scan, foreach, etc.) above fixed points. I hope to build a big enough library of loop functions that I rarely need to directly use fixpoint.

And to answer David Richerby's follow-on question: Yes, there are some interesting things we can do if all we have is fixed point combinators.

It is possible to name any function by use of secure hash, which can be convenient for content-addressable linking models. With name-based recursion, you cannot use the secure hash of a function's name to refer to itself. Besides myself, it seems Paul Chiusano aims to take advantage of this [2].
The language is much more streamable, by which I mean that program execution can proceed by processing each element in a stream of instructions then forgetting it. This is a nice feature for mobile code or remote control applications. Conventional languages model loops by jumping backwards, which requires the computer hold onto the code (i.e. stored program computing).

Use of fixed point combinators is not a sufficient condition for these features. Other aspects of the language must also align. But fixed point combinators do not entangle program semantics with the namespace, which does simplify things.


Greedy algorithm for job scheduling Consider the following greedy algorithm for Job Scheduling. For each new task, assign the task to processor with the shortest uptime.

  How to prove that this algorithm has an approximation ratio of 2?

Suppose that once the algorithm is completed, processor $1$ is the busiest and assume task $l$ is the last task assigned to it. Let $s$ be the time that was used on processor $1 $ before adding task $i$. The algorithm has therefore found a valuable solution $u_1 = s + t_\ell$.

I'm stuck on how to show that:

for every $1 \leq j \leq k$ we have $s \leq \sum_{i: \alpha(i)=j}t_i$.
$s \leq 1/k \; \sum_i t_i \leq u^*$ and $t_\ell \leq u^*$ and use these results to limit $u_1$ ($u^*$  is  the optimal value).

Here is the definition of the Job Scheduling problem

Input: A set of $n$ tasks of length $t_1, t_2, \ldots, t_n \in \mathbb N$ and $k$ processors.

A feasible solution is a function $\alpha\colon \{1, \ldots ,n\} \rightarrow \{1, \ldots k\}$  which assigns each task to a processor.

The usage time $u_j$ of a processor $j$ is the sum of the lengths of all the tasks assigned to it, that is to say that $u_j = \sum_{i: \alpha(i)=j}t_i$.

We try to minimize $\max_j u_j$, that is to say the time of use of the most used processor.

You can find this algorithm analyzed at the very beginning of these lecture notes, or in these lecture notes (which consider a better variant of the algorithm but only analyze your variant), as well as in many other resources.

These are the first two hits when searching for makespan approximation.


How to access the bit at a particular index? How do I access the bit at a particular index in a number using shift operator.
Say the number is $n$.
Let the index be $i (i: 0 \le i < n).$
Rightmost bit is $0$.

The only thing I can think of is:
$def \, bitAt(n, i)$
$\,\,\,\,\,\,\,\,m = n >> i+1$
$\,\,\,\,\,\,\,\,v = n >> i$
$\,\,\,\,\,\,\,\,m = m << 1$
$\,\,\,\,\,\,\,\,if(m == v)$
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,return \, 0$
$\,\,\,\,\,\,\,\,else$
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,return \, 1$
$\,\,\,\,\,\,\,\,end$
$end$

Is there a more efficient way to do this?

This can be done by running an AND between n and a number with it's ith bit set to 1, which can be obtained by 1 << i. The result of this operation will be zero if the ith bit in n is zero, or 1 << i otherwise.

Case of zero:

n     = 10111
m     = 01000 (1 << 3)
n & m = 00000

Case of one:

n     = 10111
m     = 00100 (1 << 2)
n & m = 00100 (1 << 2)

So:

$m = 1 << i$

$\text{if}\; (n \;\&\; m == 0)$

$\;\;\;\;\text{return} \;0$

$\text{else}$

$\;\;\;\;\text{return} \;1$


Vertex cover of minimal graph I'm looking for algorithm that, for given undirected graph $G=(V,E)$, find graph $G'=(V,E')$ with minimal amount of edges that have same vertex cover as G. I mean, vertices $U$ are vertex cover of $G$ iff they are vertex cover of $G'$.
I understood that a polynomial algorithm exists, it's mean without finding the vertex cover of $G$, but I found only a non-polynomial one.

The algorithm to compute $G'$ is really easy: just return $G$.
Indeed, given any $G=(V,E)$ the only graph $G'=(V, E')$ such that $U \subseteq V$ is a vertex cover of $G$ iff $U$ is a vertex cover of $G'$ is $G$ itself.
To prove this you can show that we must simultaneously have $E \subseteq E'$  and $E' \subseteq E$.
Proof that $E \subseteq E'$: Suppose towards a contradiction that $E \nsubseteq E'$. Then $\exists (u,v) \in E \setminus E'$. The set
$U = V \setminus \{u,v\}$ is a vertex cover for $G'$ but not for $G$.
Proof that $E' \subseteq E$: Suppose towards a contradiction that $E' \nsubseteq E$. Then $\exists (u,v) \in E' \setminus E$. The set
$U = V \setminus \{u,v\}$ is a vertex cover for $G$ but not for $G'$.


What does "refuting random 3CNF" formulas mean? Intuitively, recall what 3CNF formulas mean:

Its a boolean formula with conjunctive normal form (i.e. formula of ANDs of clauses with ORs) with no more than three variables per conjunct.

I was reading a paper that said:

  under a widely believed assumption that refuting random 3CNF formulas is hard, it is impossible to efficiently learn this class using ony $O(\frac{n}{\epsilon^2})$ examples.

however, I wasn't sure what "refuting random 3CNF formulas" even meant so I was having a hard time understanding the sentence. Someone know what that means?

A random 3CNF with $n$ variables and $m$ clauses is obtained by picking $m$ clauses uniformly at random among the $8\binom{n}{3}$ different clauses. It is known that there exists a constant $C$ such that when $m = Cn$, a random 3CNF is unsatisfiable with high probability; it is strongly suspected that there exists a best such constant $C$, which is known experimentally to be about $4.2$.

It seems, therefore, that if I give you a random 3CNF with $n$ variables and $100n$ clauses, it should be easy to prove that it's unsatisfiable (unless you're very unlucky). However, the best such algorithm, due to Feige and Ofek, only works for $m = \Omega(n^{1.5})$. The best non-deterministic algorithm, due to Feige, Kim and Ofek, only works for $m = \Omega(n^{1.4})$.

One can state many conjectures of the form "refuting random 3CNF formulas is hard". The weakest would state that for every $C > 0$, there is no polynomial time algorithm that, given a formula, answers either unsatisfiable or don't know, and (i) answers unsatisfiable with high probability when given a random 3CNF with $n$ variables and $Cn$ clauses, (ii) answers unsatisfiable only for unsatisfiable formulas.

Stronger conjectures would work for $n^{1+\epsilon}$ clauses for some $\epsilon > 0$, and for non-deterministic polynomial time algorithms.


Remove parallel edges in a directed graph in linear time Is there a $O(|V|+|E|)$ algorithm to find and remove all parallel edges in a directed graph? I'm stuck because each idea I've thought of boils down to $deg(v)^2$ comparisons per $v$ which is of course not linear.

Thanks.

Get a list of the edges, this should take no more than $O(|V|+|E|)$ in usual representations.

Run through the edges and check/add them to adjacency matrix represented as hash-table or sparse array. If an edge's entry has been set you know they are parallel. Do some constant time operations during and after iteration to handle the parallel edges how you'd like.


Is there any example of automatas (or similar) systems that emerge complex internal structures on its own? Automatas are turing-complete grid-based systems with progression rules on which we can encode arbitrarily complex structures. For example, this is a "glider gun" on Conway's Game of Life:

Due to turing-completeness, with enough efforts, one could encode fully-featured structures, such as machines that claimed territories on the grid and defended those against intrudes. As much as that is possible by human design, the system will not emerge complex structures on its own. That is, you can't start a Game of Life with random initial conditions, leave it running for years and hope that, when you come back, you'll be able to observe gliders and other complex structures emerged naturally.

My question is: is there any known computing system in which complex structures emerge naturally from just running it for long enough?

It seems very hard to define the phrase "internal structures that defend their own existences" in a rigorous or precise way, so it is not clear that the question is well-defined.  However, some very simple systems can admit behavior that might be described in these terms.

For instance, consider Conway's game of life.  It is known to allow for replicators: i.e., there are self-replicating patterns which create a complete copy of themselves.  Replication can be thought of as a "strategy" for "defending your own existence"; if you spawn many copies of yourself, then even if someone messes up one of the copies, the other copies will still exist.

So, to the extent that the phrase "internal structures that defend their own existence" is well-defined, self-replicators in Conway's game of life might be considered a form of internal structure that will defend its own existence.

Conway's game of life is very simple.  Another very simple example is Rule 110, which is an extremely simple cellular automaton.  It is known that Rule 110 is Turing complete, which means that it is possible to simulate Conway's game of life in a Rule 110 cellular automaton, which means that a Rule 110 cellular automaton can be argued to allow for "internal structures that defend their own existence".  It's probably going to be hard to find a system that's much simpler than a Rule 110 cellular automaton.

In general, we should probably be careful about anthromorphicizing the behavior of computational systems like this.  Just because they behave in ways that resemble the behavior of people or animals doesn't necessarily mean it's necessarily going to be super-meaningful to describe them as acting with a 'purpose' (like self-defense).  Ascribing human motivations or emotions to them runs the risk of misleading our intuition.


Minimal date interval cover algorithm The problem involves date intervals filtered by days of week. For example, the filtered interval {2001 APR 1 - 2001 APR 30, 17} corresponds to all Mondays and Sundays between April 1 and April 30. Here is the problem: given a collection of filtered date intervals, find a minimal collection of such intervals that cover exactly the same set of dates.

Initially, I naively assumed that this can be solved by sorting the intervals by start dates and merging consecutive intervals, if possible. Here is a counterexample to this approach. Consider the date interval given by the pattern $56712345671234$, where each number stands for a day of week. Assign zero-based indices to the dates in this pattern. The set of dates covered by intervals $\{0-2, 567\}$, $\{3-9, 1234\}$, $\{10-13, 12\}$ can be covered by the collection $\{0-6, 1234567\}, \{7-13, 12\}$. The merging algorithm will fail to merge any intervals and will output three intervals as the minimal cover instead of two.

Is there a well-known algorithm for this problem? Can it be solved in $O(n \log n)$ where $n$ is the number of input intervals?

This can be solved in $O(n \log n)$ time by a greedy algorithm.  Take the earliest week you need to cover (that isn't covered yet).  Pick the set of days-of-the-week that you need to cover in that week.  Choose a filtered data interval that starts with that week, uses that mask, and extends as far as possible.  Add that to your collection, and repeat.

I'll let you work out the proof that it is correct, via an exchange argument.  How to prove greedy algorithm is correct may be helpful.

To make this run efficiently with a $O(n \log n)$ worst-case time, you'll need a proper data structure for storing the filtered intervals and figuring out how far you can extend an interval.  I'll let you figure that out, but a hint: a balanced binary search tree provides $O(\log n)$ running time for all basic operations.


What is the Big O estimate of a nested for loop? I am trying to figure out what the big o estimate of the following for loop is.

for(int i = 10; i to 100; i++){
for(int j = 1; j to i; j++){
for(int k = 1; k to j; k++){
s=s+i+j;
}
}
}

I was thinking that the two inner loops run n times but I am unsure about the first loop.

What would the Big O estimate be for this code?

The whole thing is $O(1)$. This is because the outermost loop has an upper bound of 100 i.e. it is constant, and it bounds the middle loop, which bounds the inner loop. There's a little bit of tricky math to figure out exactly how many times the loop is run, but you can know exactly how many times it is run.

The first hint that this is $O(1)$ is that there are no "free" variables. Pretend the code was linear. What would it be linear in terms of? There are no input parameters. We create $i$,$j$ and $k$, and their values don't change based on some input parameter.


How precise is the statement "STLC is the internal language of CCCs"? I'm studying some basic category theory in the context of type theory and came across the statement "simply typed lambda calculus is the internal language of cartesian closed categories". However terms and substitutions in the internal language of CCCs are the same data type, unlike in (traditional) STLC. Speaking in Agda, we have

π¹ : ∀ {Γ σ} -> Γ × σ ⊢ Γ
π² : ∀ {Γ σ} -> Γ × σ ⊢ σ
_[_] : ∀ {Γ Δ σ} -> Γ ⊢ σ -> Δ ⊢ Γ -> Δ ⊢ σ

where π¹ is supposed to be a substitution constructor and π² and _[_] are supposed to be term constructors.

This additional first-orderness allows to abstract over substitutions, so we can e.g. write (using de Bruijn indices)

I : ∀ {Γ σ} -> Γ ⊢ σ ⇒ σ
I = ƛ var 0

silly : ∀ {Γ Δ σ} -> Γ ⊢ Δ ⇒ σ ⇒ σ
silly = ƛ (I [ var 0 ])

I don't know what silly is, but it doesn't look like a regular lambda term to me.

So is the internal language of CCCs actually more expressive than STLC or am I misunderstanding something?

Cartesian closed categories correspond to the simply typed lambda calculus with products.  Your silly function is just $\lambda x.\lambda y.y$. If you want something that directly corresponds to the simply typed lambda calculus without implying products check out this paper by Bart Jacobs: Simply Typed and Untyped Lambda Calculus Revisited.

Let's instantiate your silly term and spell out what it looks like in type theoretic notation.

First, we're using _[_] at type $(\sigma \vdash \tau \Rightarrow \tau) \to (\Gamma\times\sigma\vdash\sigma) \to (\Gamma\times\sigma\vdash\tau\Rightarrow\tau)$.  As a rule and placing in the terms, we get:
$$\frac{z : \sigma \vdash \lambda y:\tau.y : \tau\Rightarrow\tau \qquad \Gamma, x:\sigma\vdash x:\sigma}{\Gamma,x:\sigma\vdash (\lambda y:\tau.y)[z\mapsto x]:\tau\Rightarrow\tau}$$
where $M[z\mapsto N]$ means "substitute $N$ for $z$ in term $M$".  Of course,  substituting for a variable that doesn't occur does nothing.  So, in type theory, the above is (often by definition of substitution) equivalent to just $\Gamma,x:\sigma\vdash(\lambda y:\tau.y):\tau\Rightarrow\tau$.  (Closely relatedly, weakening is also often transparent in type theory.)  We then lambda abstract to get silly.

As a potential further insight, structural rules like $(\lambda y:\tau.M)[x\mapsto N] \equiv (\lambda y:\tau.M[x\mapsto N])$ with $y$ not free in $N$ come from naturality.  This particular case comes from naturality of currying (if you spell it out, you'll see how the "$y$ not free in $N$" part is handled).

However, in this case it was a bit of a fluke that this worked out.  In general, the second argument to _[_] should be a substitution, i.e. an arrow from contexts to contexts.  In this code, a context is effectively represented by a left nested tuple (ending in an empty tuple).  So if the second argument to _[_] does not return a left nested tuple, then _[_] will not behave like substitution.  For example, the expression var 0 [ var 1 ] does not correspond to $$x:\sigma, y:\sigma \vdash x[x\mapsto y] : \sigma$$ like we might think, but rather to $$x:\sigma\times\sigma, y:\sigma \vdash \mathtt{snd}(x) : \sigma$$
This second interpretation is an artifact of this particular implementation that was exposed by failing to meet the precondition of _[_].  We would get the intended behavior had we written something like var 0 [pair unit (var 1)].  It would be cleaner and closer to typical STLC syntax to have _[_] take a vector of arrows that get tupled together in a left nested manner.

That this confusion between types and contexts is so easy is particular to CCCs.  Most categorical semantics have a strict distinction between types and contexts; they live in separate categories.  This is true of the semantics in the above mentioned Bart Jacobs paper.  However, this conflation of types and contexts in CCCs makes it possible to discuss the categorical semantics without needing to introduce notions like indexed categories or fibrations.


Composition for Functional Depedencies Suppose I have the following Functional Dependencies for a Relational Model:

$A \to C$
$B \to C$

According to the composition rule for functional dependencies we have:
If X → Y and Z → W, then XZ → YW

For the case above would it be correct to say:

$AB \to CC$

Leads to:

$AB \to C$

Would the composite $CC$ be the same as just $C$? And for a relational model would it be proper to separate $C$ into a relation such that $AB$ is the Primary Key? Or should I simply drop either of the relations $A \to C$ or $B \to C$?
I was told by my database professor that $AB \to C$ is wrong and I should dropped one of them when I have created a Logical Data Model. But I don't understand how what I said above is wrong.

In a relational model, CC would be redundant, it's like saying that 1 = 1 * 1.
Using a real example, if A = person ID, B = person fingerprint, C = person name,
then you would say that "given a person ID and fingerprint, the name of a person is Bob, Bob is the name of the person".
Thus, I would argue that AB -> CC and AB -> C are equivalent, and the composition AB -> CC is not necessary.

given both A -> C and B -> C, then If you know did a search for "Bob" in the database, you would get both results for person ID's and person fingerprints. If fingerprints are stored together with person ID's, this means that your search result has one redundant entry for every result. Therefore it is much better design to only have the relation A -> C or B -> C to reduce the number of lookups. If A and B are in seperate entities, however, you might want both relations.

If you only specify AB -> C, you would not be able to use A -> C or B -> C, which are both true. Therefore you should not put this statement alone. However, if A -> B and B -> A, it might be valid, but usually inefficient. Now, to find AB given C (searching for all relations that match "Bob"), you need to lookup both person ID and person fingerprint, and match these two together (checking if A -> B or B -> A). It is faster to just check one attribute (look for only A or B, not both).


Training a HMM with Baum-Welch gives different results across runs I am running a Baum-Welch HMM algorithm (in R). The sequence vector contains a series of observations which have been gathered from a dataset where the data has 17 states.

I can successfully run the HMM algorithm and it converges without any problems when I set pseudo count to 1e-09, below that the algorithm fails.

My question relates to the Baum-Welch algorithm and local minima. When I run the algorithm and obtain the estimates for the emission matrix and transition matrix, I then use these as inputs to calculate the posterior probability of a sequence.

That is all fine except that when I redo all of the above (in a new R session) I get completely different posterior probability estimates. Is this because the BW algorithm is getting stuck in different local minima each time?

It is impossible to locate the issue for sure without inspecting the implementation and results in more detail than is ontopic here. For instance, numeric algorithms always have potential issues related to the precision of the used number format, especially when dealing with (very small) probabilities.

That said, two notes.

Baum-Welch does only find local optima.
Insufficient training data can cause parameter estimations to vary wildly.

So I recommend you try more training data if possible. Otherwise, just run the algorithm many times and pick the best model (according to the likelihood of the training data according to the resp. model) you find.


Courcelle's Theorem: Looking for papers I am looking for an easy and introductory paper on the proof of Courcelle's Theorem. I am also interested in its connection to parameterized complexity regarding the treewidth.

I am only a beginner in this field.

Any suggestions?

There's a soft introduction in Rolf Niedermeier's book Invitation to Fixed Parameter Algorithms. Daniel Marx also has quite a few slides available on his homepage that contain short examples of modeling a problem in MSOL. One set of relevant slides is here. For more links, see a related question on CSTheory.


Grammar and Real-numbers I am curious about following question. I've read other threads but the problem is slightly different:
Is the set of real numbers a language?

So my question is:

If I have a grammar, as defined in https://en.wikipedia.org/wiki/Formal_grammar#The_syntax_of_grammars

G = (P,N,S,$\sum$)

P-production rules
N-non terminals
S- StartSymbol-
$\sum$ -terminal symbols

is it possible to have the set of real numbers in the set of terminal symbols?
The definition of a grammar on wikipedia says no.

Is it possible to define it otherwise?

You could use the digits $\{0,\dots,9\} =: \Sigma$ as alphabet and consider infinite words. A word corresponds then to a real number. Those are known as $\omega$ languages link. There are omega-regular languages too.

Edit: The set of all real numbers, $\Sigma^\omega$, forms an $\omega$-regular language of course.


Creating a Grammar that is equivalent to "RegEx A, RegEx B, or BOTH" I have the following problem, create a Grammar on the Language {1,0} that accepts

  "strings with a length divisible by 3, or strings with a number of 0s divisible
  by 3, or BOTH".

I created grammars for each part, but I'm not sure how to account for the "BOTH" clause.

I started by making a regular expression:

1*(01*01*01*)+|((0|1)(0|1)(0|1))+

Then I made the following Grammars for each of the two main parts:

1*(01*01*01*)+

becomes

S_1 -> 1F | F
F   -> 1F | 0G
G   -> 1G | 0H
H   -> 1H | 0M
M   -> F | (empty)

and

((0|1)(0|1)(0|1))+

becomes

S_2 -> 0C | 1C
C   -> 0D | 1D
D   -> 0E | 1E
E   -> S | (empty)

My question is, if I just use the central or in the regular expression and start the complete Grammar by branching to one of the two Grammars I made with no cross over*, will it somehow potentially compromise the "or BOTH" requirement in some cases? Or is that extra requirement just a red herring and will be necessarily satisfied by covering both of the base requirements? As far as I can tell, both are more or less completely independent of one another.

*ie just tack the two together with this at the start:

S -> S_1 | S_2
...

$S \to S_1 | S_2$

That is correct. A grammar doesn't care which derivation it used, or how many could have been used, as long as at least one derivation is valid.

Now if the question said but not both, then it would get complicated!


Why is $\sum_{j=0}^{\lfloor\log (n-1)\rfloor}2^j$ in $\Theta (n)$? I am trying to understand summation for amortization analysis of a hash-table from a MIT lecture video (at time 16:09).

Although you guys don't have to go and look at the video, I feel that the summation he does is wrong so I will attach the screenshot of the slide.

If you have a series of numbers that are consecutive power of 2s, like $1+2+4+8+16+\cdots+2^k$ you get as sum $2^{k+1}-1$. You can either see this by looking at the formula for the geometric series or you can prove this by induction.

Then the statement of the lectures follows, since here $k=\lfloor \log (n-1) \rfloor$. Therefore the sum is less than $2n$.


Is this possible that quantum computer will be able to violate the Church thesis? After reading Church's thesis, and godelization theory, it seems everything is futile, is this really true, all the machines we are making machine which is same as before, bounded to not solve halting problems, in more simple terms can quantum computer do anything that a Turing machine can't?
PS: In book named Elements of theory of computation first edition, you will find Godelization otherwise it is redacted since second edition reason unknown but chapter 5 named Church Thesis is highly altered since second edition.

No.  A classical computer can compute anything a quantum computer can do, given long enough.  There are simple methods of simulation that cause an exponential slowdown, which suffices to show that if it is decidable on a quantum computer, it is decidable on a classical computer.  (We don't know whether the there might be other faster ways of simulating a quantum computer on a classical computer, but that doesn't affect decidability.)


Efficient algorithm to determine if a lambda calculus term is equivalent to one without a given free variable Consider the following problem: given a lambda calculus term $t$ and free variable $v$ determine whether $\phi(t,v)$, where $\phi(t,v) := \exists t'. t' \equiv t \land v \notin FV(t')$.

This problem is undecidable. To prove this, assume the contrary. We define a term $s$ as follows:

$$s x \equiv \lambda n.j. j y$$

if $x$ is an encoding of the configuration of a Turing machine and $y$ is the encoding of the configuration the Turing machine transitions into in one step and

$$s x \equiv \lambda n.j. n$$

if $x$ is an encoding of the configuration of a Turing machine that has halted.

Now define the term $t_M$ as follows:

$$t_M := Y (\lambda f.x. s x (\lambda a.b. b) f) i_M$$

where $i_M$ is the encoding of the initial configuration of $M$, and $Y$ is the fixed point combinator.

If $M$ halts, $t_mv \equiv (\lambda b. b)$. Otherwise, $t_mv$ does not have a normal form, and every term equivalent to it has $v$ in it. Therefore, $\phi(t, v)$ iff $M$ halts. This algorithm can be used to solve the halting problem, which is a contradiction.

On the other hand, it is semidecidable. For any $t$ and $v$, simply enumerate the $t'$ such that $t' \equiv t$. If a $t'$ is enumerated such that $v \notin FV(t')$, output yes and halt. This algorithm outputs yes iff $\phi(t, v)$.

That said, this algorithm is not very efficient, since you have to use an enumeration that enumerates all $t'$ such that $t' \equiv t$. Is there an efficient algorithm to semidecide whether $\phi(t,v)$ is true?

EDIT: We'll say an algorithm for determining $\phi(t,v)$ is efficient if, when $\phi(t,v)$ is true, it halts in an amount of time that is a polynomial of the minimum number of reduction and conversion steps required to eliminate $v$ from $t$.

An approach one might consider is to normalize $t$, and then check if $v$ is free in the result. Although this would be efficient, it would not be correct. For example, this algorithm would not halt on the input $(\Omega ((\lambda a.b. a) \Omega v), v)$ (where $\Omega := (\lambda x. x x)(\lambda x. x x)$), but $\phi(\Omega ((\lambda a.b. a) \Omega v), v)$ is true.

Another approach would be to use some reduction strategy, and then to check after each step if $v$ is free in the term produced by that step. Although I think this is a good direction to take, it should be noted that neither normal order reduction nor applicative order reduction would work. To see this, consider the input $(t_M(t_Nv),v)$. If $M$ diverges but $N$ halts, $\phi(t_M(t_Nv),v)$ is true, but normal order reduction will never eliminate $v$. Likewise, if $M$ halts but $N$ diverges, $\phi(t_M(t_Nv),v)$ is again true, but applicative order will never eliminate $v$.

The input $(t_M(t_Nv),v)$ is rather tricky in general. To solve this input, an algorithm would probably need to attempt to normalize $t_M$ and $t_N$ in parallel, outputting yes if either normalizes. Attempting to normalize $t_M$ first or normalize $t_N$ first will not work.

On the other hand, by the Church-Rosser theorem, we only need reductions, no expansions. We never need to "undo" a reduction step to eliminate a variable. That is because if $t' \equiv t \land v \notin FV(t')$, there is some term that both $t$ and $t'$ reduce to. It will not contain $v$, since $t'$ does not, and reductions never introduce free variables. Since $t$ also reduces to this term, $t$ can be reduced to a term without $v$.

Alpha conversion does not make a difference. It appears that eta conversion is also irrelevant.

You can't semi-decide a non decidable problem in an efficient way.

Suppose that you have an algorithm $A$ which semidecides such a problem in, say, $T(n)$. I.e. every word in the problem is accepted within $T(n)$ steps. Assume that $T(n)$ is bounded from above by any computable total function $g(n)$ (say $2^{2^n}$, which allows $A$ to range over any efficient algorithm).

Then, the problem is decidable: run $A$ for at most $g(n)$ steps, and accept if $A$ accepts, otherwise reject.

Contradiction. QED

Asymptotically, a semidecider of a non recursive problem can never be efficient. (Unless we choose another definition of "efficient" than "low worst-case complexity", I guess)


How to find the supremum over all the "good" (interior) polytopes for a given set of 3D points? Let $S \subset \mathbf{R}^3$ be a set of points in 3D and let $O=(x_0,y_0,z_0)$ be the origin/point of reference.

We consider a convex polytope $P$ good / interior if:

$P$ is wholly contained within the interior of the convex hull of $S$:
$P \subsetneq \text{convexhull}(S)$.
$O$ is contained within the interior of $P$, namely: $O \in P$.
none of the points in $S$ are in $P$ namely $S \cap P = \emptyset$.

Out of all good convex polytopes, we want to find either the maximum (supremum) of their volumes, i.e. $\sup  \text{Vol}(P)$ where $P$ ranges over good polytopes.

Here is a 2D modest illustration (the green polytope might not be really the optimal):

The black dots are the set $S$, the origin $O$ is in the middle. The red lines go through the points in $S$ which define the boundary of $S$ (not a good polytope) and the green lines go through a good polytope.

Is there an efficient algorithm to compute this best convex and non-convex polytopes for a given set $S$ of points and origin $O$?

I would like to formulate this problem as an optimization problem or to come up with some algorithm using triangulation, $\alpha$-shapes or $\beta$-skeleton geometric transformation + convex hull, linear programming, maybe working in the dual space? etc.

One idea which I have is "pumping down" the convex hull of Delaunay Triangulation:

  DT $\leftarrow$  delaunayTriangulation($S \cup O$)

  CH $\leftarrow$  convexHull(DT)

  while  Not empty(DT) and $O \notin CH$:

  $\quad$ i.  previousDT $\leftarrow$ DT

  $\quad$ ii. update DT $\leftarrow$ DT $\setminus$ CH

  return previousDT

EDIT: I think what I am looking for in a one-liner of math symbols is:

$$\text{argmax}_{P} \text\{\text{Vol}(P) \,  | \, O \in P \setminus \partial P \, ; \,
 S\cap P = \emptyset  \, ; \, P \subsetneq \text{convexhull}(S) \} $$

Where $\partial P$ is the boundary of a polytope $P$.

What I ended up doing is the following:

Given a set of points in $\mathbf{R}^3$ $S$, and a single point as origin, $\mathbf O$ do the following:

Init empty set $S'$.
$r = \max\{ ||\mathbf x - \mathbf O ||^2_2 \, , \,\,   \mathbf x \in S\}$
Create a mapping $F(x): S\to S'$ where $\mathbf x \in S \to \frac{r^2}{||\mathbf x - \mathbf O\|^2} (\mathbf x- \mathbf O)$
$CH_{S'} \leftarrow $ the points in $S'$ which form convex hull of $S'$ (the sphere inverted set $S$)
Init the interior points set, $IP$ $\leftarrow$ $F^{-1}(s'\in CH_{S'})$ to find the points in $S$ whose sphere inversion points were in $CH_{S'}$.
Use Delaunay triangulation to find the volume of the the convex hull of $IP$

Matlab code:

%% Init
N=20;

S1 = cell(1, N);
for k = 1:N, S1{k} = 30*rand(1, 3); end
S2 = cell(1, N);
for k = 1:N, S2{k} = 30*rand(1, 3); end

M1 = cat(3, S1{:});
M2 = cat(3, S2{:});
M  = permute(cat(1, M1, M2), [1, 3, 2]);

O=[0.5,0.5,0.5];

NearestIntersectionPoints = cell(1,N);
for k = 1:N
    tmp1 = M(1,k,:); tmp2 = M(2,k,:);
    v1=tmp1(1,:); v2=tmp2(1,:);
    [d, intersection] = point_to_line(O, v1, v2);
    NearestIntersectionPoints{k} = intersection;
end

MHull = cat(3,NearestIntersectionPoints{:});
X=MHull(:,1,:); Y=MHull(:,2,:); Z=MHull(:,3,:);
R=[ X(:) Y(:) Z(:)];

X=[X(:)]; Y=[Y(:)]; Z=[Z(:)];
DT = delaunayTriangulation(X,Y,Z);

rSquared = (X-O(1)).^2 + (X-O(2)).^2 + (Z-O(3)).^2;

q = rSquared/max(rSquared);
xx=X./q; yy=Y./q; zz=Z./q;

figure
plot3(X,Y,Z, '.', 'MarkerSize',15);
hold on
[k,v] = convhull(X,Y,Z);
v
trisurf(k,X,Y,Z,'Facecolor','red','FaceAlpha',0.1)

figure
[k,v] = convhull(xx,yy,zz);

trisurf(k,X,Y,Z,'Facecolor','red','FaceAlpha',0.1)
hold on
plot3(X,Y,Z, '.', 'MarkerSize',15)
uniqueK = unique(k)
DTinterior = delaunayTriangulation(X(uniqueK),Y(uniqueK),Z(uniqueK));
DTexterior = delaunayTriangulation(X,Y,Z);

[kin, vin] = DTinterior.convexHull;
[kext, vext] = DTexterior.convexHull;

function [d,intersection] = point_to_line(pt, v1, v2)
      a = v1 - v2;
      b = pt - v2;
      d = norm(cross(a,b)) / norm(a);
      theta = asin(norm(cross(a,b))/(norm(a)*norm(b)));
      intersection = v2 + a * cos(theta);
end

Demo in 2D:

close all
N=20;
R=[1, 5];
center=[0, 0];
x=zeros(length(R),N);
y=zeros(length(R),N);
theta=linspace(0,2*pi,N+1);
theta=theta(1:end-1);

for i=1:length(R)
    x(i,:)=R(i)*(randn+1)*cos(theta+rand) + center(1);
    y(i,:)=R(i)*(randn+1)*sin(theta+rand) + center(2);
end

% Concat all the arrays into one set
x=[x(1,:) x(2,:)]; y=[y(1,:) y(2,:)];
rSquared=x.^2 + y.^2;
q = rSquared/max(rSquared)^2;
xx=x./q; yy=y./q;

k = convhull(xx,yy);
plot(x(k),y(k),'r-',x,y,'b*')


Find the minimum N such that the sum of beauty of all numbers from 1 to N is at least X The beauty of a number is defined as follows :-

public int beauty(long number)
{
     int count = 0;

     while( number > 0 )
     {
         count += (number & 1);
         number = number / 2;
     }

     return count;
}

Given X, we need to find the minimum N such that the sum of beauty of all numbers from 1 to N (inclusive) is at least X. X may be as large as upto 10^18 and there are 2*(10^4) test cases.

As far as I have understood, the beauty of the number is the count of set bits in the integer. So we need to find the sum of count of set-bits from 1 to N. But numbers such as X = 10^18 give the values 10^15 for N. It is not feasible to run loop from 1 to 10^15. Is there a better algorithm ?

Notations :

$b(x)$ is the beauty of $x$.
$S_c(n) = \sum_{x = 0}^{2^n-1} (b(x)+c)$ where $c\in\mathbb N$
$\tilde O(\log t)$ : polylogarithmic in $t$

Argument :

Let's first show that $S_c(n)$ is easy to calculate for any $c,n\in\mathbb N$. Each number in $[\![0, 2^{n-1}]\!]$ has at most $n$ bits, and for each $i\in[\![1, n]\!]$, exactly half of the numbers below $2^n$ have the $i$-th bit set to 1. Therefore, we can rewrite
$$\sum_{x =0}^{2^n-1} b(x) = \sum_{i = 1}^n 2^n/2 = n\cdot 2^{n-1}$$
(in 0, the result is 0). This leads to :
$$ S_c(n) = 2^{n-1}\cdot (c+2n)$$
Since $S_c(n)$ grows exponentially and is computable in $O(n)$, it takes $\tilde O(\log X)$ time to find the (unique) $n$ such that \begin{equation}S_c(n)\le X< S_c(n+1)\end{equation}

We'll note $n_0$ this $n$ for $c = 0$. One should notice that this $n_0$ is the index of the leftmost bit set to 1 in $N$
$$\sum_{x = 0}^N b(x) = \sum_{x = 0}^{2^{n_0}-1} b(x) + \sum_{x = 2^{n_0}}^N b(x)$$
Moreover, $N<2^{n+1}$, so each $x$ in the rightmost sum has $n$ bits and the leftmost bit set to 1, i.e. :
$$\sum_{x = 2^n}^N b(x) = \sum_{x = 0}^{N-2^n} b(x) + 1$$

We therefore get a recursive call : we can find the index of the leftmost bit set to 1 in $N-2^n$ by finding $n_1$ such that $S_1(n_1)\le (X- S_0(n_0)) \le S_1(n_1+1)$

This lends the following algorithm :

s(n,c) =
    if n = 0 then c
    else (2^(n-1)*(c+2*n))

smallest_n(x,c,n) = //We shall call this function with n = 0
    if s(n+1,c) > x then n
    else smallest_n(x,c,n+1)

sum_beauties_above(x,c) =
    if x = 0 then 0
    else
        let n = smallest_n(x,c,0) in
        let n' = sum_beauties_above(x - s(n,c),c+1) in
        2^n + n'
sum_beauties_above(x,0)

the first function takes $O(n)$ time, the second takes $\tilde O(\log X)$. The main function calls itself as many times as $N$ has bits set to $1$, which is bounded by $\log N\le \log X$, and each call has complexity $\tilde O(\log X)$, so we keep a polylogarithmic complexity in $X$.

However, this has been written in functionnal programming style, and is not tail-recursive, therefore, it is highly suboptimal, but this way of writing seems easier to understand, and one should take care of optimization.


Isn't linear time O(n)? In the question in this video about quicksort luckily picking the median in each recursive call. Tim Roughgarden, the presenter, says at 11:22

Partition needs really linear time, not just $O(n)$ time.

What does he mean here? I thought linear time is $O(n)$. Does he mean $\Theta(n)$ or something else? I see how partition in quicksort here would be $\Theta(n)$ but I don't get the part that says "not just $O(n)$ time".

Usually we call statement $A$ stronger than $B$ when $A$ implies $B$: $A \Rightarrow B$ (weaker-stronger). In other words, $B$ is weaker than $A$.
When the presenter is speaking about linear time for partition, this is a stronger statement than $O(n)$ time. All linear functions are in $O(n)$, but it also contains non-linear functions.
For example: $\sin n, \frac{1}{n}, \sqrt{n} $ are all in $O(n)$, but they are not linear. As was written in a comment, $O(n)$ is the set of functions bounded by linear functions, but not the set of only linear functions.
To be linear gives more information than to be in $O(n)$, to be in $\Omega(n)$, even to be in $\Theta(n)$.


Finding The Inverse of The Modulo Operation I created an algorithm to convert a hexadecimal digit into an alphanumeric string, but now I want to create the inverse of this algorithm. The algorithm, in short, is as follows:

  hexadecimal digit % length of alphanumeric character array = index in alphanumeric character array

For example, the algorithm takes hex digit 4e (78 in decimal), mods it with the size of an alphanumeric character array (size: 62), and returns decimal number 16, which is a G. The alphanumeric character array in this example is structured like the following: (0-9, A-Z, a-z).

  In short this example is written as: (4e)78 % 62 = 16(G)

The inverse of this algorithm is what I hope to achieve and from various tests, it seems multiple results can occur, but my ultimate goal is to end up with a reversible algorithm, where, for example, hexadecimal digit 4e gets converted to letter G then back again to 4e when put through the inverse algorithm. From the example, I developed a possible description of the inverse algorithm:

  Suppose we have a modular equation. Let x be the dividend, y be the divisor, and r be the remainder. r and y are given where r=16 and y=62. Find an x such that x % y = r or x % 62 = 16.

The solution that I tried: Bruteforce the dividend

The dividend will never be out of the closed interval [0, 255] since a pair of hexadecimal numbers can have a maximum value of ff, which is 255 in decimal. Thus, if we test x's against the modular equation until we get an equal remainder, we can derive the dividend.

However, this solution will result in multiple possible x values due to the modulo operation causing a wrap-around effect in the alphanumeric array, which means multiple values can cause the equation to hold true. In the case of the provided example, the proposed solution results in the following dividends: 16, 78, 140, and 202. The second dividend is the correct one and the one that results in the algorithms being reversible. However, the issue is finding it, since the correct one isn't directly known at the time of running the inverse algorithm.

Any help in devising either a solution to my proposed method or a different one would be greatly appreciated. Thanks.

I ended up solving my issue, but not in the way I expected. The solution involves the inherent halving of the output string. Using this, one can simply calculate the quotient of dividing x by y and using that as the second alphanumeric character, forming a pair. In the given example, the resulting G would become G1 because the modular arithmetic involved looping over the alphanumeric character array once.

The algorithm is now as follows: x % y = r + (x / y), which is easily reversible by bruteforcing the possible dividends and simply selecting the correct one using the second character in the alphanumeric pair. Thus, this modified algorithm is now reversible and has been proven to work with the example given in the original question.


Direct vs. Random Access Would someone please  clarify for me the difference between direct and random access?

Specifically, why does this Wikipedia article on Direct Access Storage Devices distinguish between the two:

  The direct access capability, occasionally and incorrectly called
  random access  (although that term survives when referring to memory or RAM),

whereas this article on random access doesn't:

  In computer science, random access (sometimes called direct access) is
  the ability to access an element at an arbitrary position in a
  sequence in equal time, independent of sequence size.

When you speak about direct access in small amount of time that could also be logarithmic, you speak about secondary devices, so hard disks, floppys, USB flash drives, etc.

When you speak about random access you mean that access time to any part of memory is constant. This is very hard to achieve with secondary devices, but easier with primary ones.


Algorithm for checking if a list of integers is pairwise coprime Are thre any efficient algorithms for checking if a list of integers is pairwise coprime, or would a more general algorithm be the best option available?

First, two facts about coprime integers:

Iff $a$ and $b$ are coprime, then $ab = \mathrm{lcm}(a,b)$
Iff $a$ is coprime to both $b$ and $c$, then $a$ is coprime to $bc$

It follows from this that a set of distinct integers $\{a, b, \cdots z\}$ is pairwise coprime if its product is equal to its least common multiple.

You can compute the least common multiple by using the following identity:

$$\mathrm{lcm}(a,b,c) = \mathrm{lcm}(a,\mathrm{lcm}(b,c))$$

Assuming you have $n$ numbers with $k$ digits each, and multiplying/dividing/modding two numbers is $O(1)$ (which may or may not be a good assumption depending on your model), then:

Calculating the product of your set takes $O(n)$
Calculating the gcd of two numbers takes $O(k)$
Calculating the lcm of two numbers thus also takes $O(k)$, by reduction to gcd
So calculating the lcm of your entire set takes $O(nk)$

Thus, the time complexity of the entire algorithm is $O(nk)$.


The first Turing machine Does anyone know how efficient was the first Turing machine that Alan Turing made? I mean how many moves did it do per second or so... I'm just curious. Also couldn't find any info about it on the web.

"Turing machines" (or "a-machines") are a mathematical concept, not actual, physical devices. Turing came up with them in order to write mathematical proofs about computers, with the following logic:

Writing proofs about physical wires and switches is extremely difficult.
Writing proofs about Turing machines is (relatively) easy.
Anything physical wires and switches can do, you can build a Turing machine to do (*) (**).

But Turing never built an actual machine that wrote symbols on a paper tape. Other people have, but only as a demonstration: here's one you can make out of a business card, for example.
Why did he never build a physical Turing machine? To put it simply, it just wouldn't be that useful. The thing is, nobody's ever come up with a model of computation that's stronger than a Turing machine (in that it can compute things a Turing machine can't). And it's been proven that several other models of computation, such as the lambda calculus or the Python programming language, are "Turing-complete": they can do everything a Turing machine can.
So for anything except a mathematical proof, it's generally much more useful to use one of these other models. Then you can use the Turing machines in your proofs without any loss of generality.
(*) Specifically, any calculation: a Turing machine can't turn on a lightbulb, for example, but lightbulbs aren't very interesting from a theory-of-computation standpoint.
(**) As has been pointed out in the comments, Turing's main definition of "computer" was a human following an algorithm. He conjectured that there's no computation a human can do that a Turing machine can't do—but nobody has been able to prove this, in part because defining exactly what a human mind can do is incredibly difficult. Look into the Church-Turing Thesis if you're interested.


complexity of modal logic axioms I am writing a paper in which I want to include complexity results for different modal logics and possibly add a reference to a specific paper.

At the moment I have the following:

K- no restrictions on the frame, NPComplete

T- reflexive, NPComplete

K4- transitive, PSpaceComplete

S4 and S4.3 also PSpaceComplete

S5- symmetric, transitive and reflexive, NPComplete.

I am not able to find any results regarding complexity of the following axioms for modal logic:

D- serial

KB- symmetric

B- reflexive, symmetric

The above 3 modal logics are important for me and I really need the complexity results with a specific paper. If anyone could help me out here it would be great thanks.

You might find interesting some of the results in On the Complexity of Fragments of Modal Logics by Linh Anh Nguyen (in Advances in Modal Logic, 2004: 249-268). A version of the paper is available in the home page of Nyugen.

And probably you are already familiar with A guide to completeness and complexity of modal logics by Joseph Y. Halpern and Yoram Moses (in Artificial Intelligence 54, 1992, pp. 319-379). A version of the paper similar to the published version is available in postscript and pdf in the home page of Halpern.


Unification --- most specific unifier In unification, given a set of equations, a standard problem is to compute a most general unifier (mgu). I am interested in a somewhat reversed problem. Imagine having a set of equations that do not have an mgu, like this one:

x = a
x = b

x here is a variable, whereas a and b are terms. I am interested are there any algorithms that could find a possible replacement for a and b such that the resulting equations have mgu? In the above example, that would be a -> y, b -> y, y being a variable. Lets call this a fix. I am particularly interested in most specific fixes. I could not find anything so far, but this seems like a natural problem, or not?

I found out that such a thing is called anti-unification. This problem was addressed by Plotkin and Reynolds. Here is a brief overview.


Does local optimization in a genetic algorithm decrease diversity? I want to create a hybrid genetic algorithm for a project to solve really high dimensional problems (1000+) One of my ideas is to incorporate a local optimization method within GA so each individual will be optimized to its local optima before fitness evaluation.
I've read some papers on hybrid GAs with hill climbing. So I understand that doing this will allow a somewhat fairer representation of each individual's search area by preventing the GA from obtaining bad sample from good search regions. It would obviously increase the search completeness.
But I was wondering if adding such a local optimization method would significantly decrease genetic variation? If so, should this be a big problem? And how can one prevent it?

Adding on Raphael's answer:

in a hybrid genetic algorithm (HGA), mutation plays a different  role than it does in a "pure" GA.

The local refinement requirement of the mutation operator is unnecessary in the existence of an explicit local operator allowing the mutation operator to take a more exploratory role (see Evolutionary algorithms with local search for combinatorial optimization by Mark Land).

Using larger mutations, at least large enough to move from one basin to another, is a good idea.
you can introduce parameters to control the frequency / duration / probability of local search so reaching a balance between GA and hill climbing.

Hybrid Genetic Algorithms: A Review by Tarek El-Mihoub, Adrian Hopgood, Lars Nolle and Alan Battersby contains further details.
a nice approach you can try is to perform a local search only when the best offspring (solution) in the offspring population is also the best in the current parent population (aka BOHGA:  Best Only Hybrid Genetic Algorithm).

This allows GA to explore a wide search space.


DFA to accept a String containing even number of both A and B, but rejects empty String I want to draw a DFA to accept a String containing even number of both A and B, but rejects the empty String(ε)
I have already drawn the DFA which accepts the above language, without rejecting the empty string.

I'm going to assume that your DFA has 4 states with the start state also being the singular accepting state.
Add a new (non-accepting) state where the outgoing transitions are a copy from your existing accepting start state. Make that new state the start state.
If my assumption about your existing DFA is correct then this way you should not be able to get into an accepting state with the empty string.