Maximum sub-matrix sum Given a $n\times m$ matrix $A$ of integers, find a sub-matrix whose sum is maximal. If there is one row only or one column only, then this is equivalent to finding a maximum sub-array.

The 1D version can be solved in linear time by dynamic programming. The 2D version can be solved in $\cal O(n^3)$ by looping over all pairs of columns and using the 1D algorithm on the array whose length is the number of rows in the matrix where each position $r$ holds the sum of the elements at row $r$ between the two columns.

If the matrix is given by:

\begin{pmatrix}
  1 & -2 & 0 & -1 \\
  5 & 43 & 31 & 78 \\
  -45 & -12 & 19 & 9
 \end{pmatrix}

Then for the pair of columns $(0,2)$, the max sub-matrix sum can be found by using the 1D algorithm on the array (top to bottom):

\begin{pmatrix}
  1-2+0 & = & -1 \\
  5+43+31 & = & 79\\
  -45-12+19 & = & -38
 \end{pmatrix}
Does anybody know of a $\cal O(n^2)$ algorithm for solving this problem?

I found this: Sung Eun Bae, Sequential and Parallel Algorithms for the Generalized Maximum Subarray Problem. Read pages 18-30, where it says that there are just cubic $O(nm^2)$ and sub-cubic algorithms for this problem (in general case), for example Tadao Takaoka's $O\left(n^3 \sqrt{\frac{\log\log n }{\log n }}\right)$ algorithm.

I've also found a forum comment saying that this problem can be solved in $O(N^2\log N )$ for matrices with N non-zero elements using "funny" segment tree (you can ask commentator about details).


Algorithm to get any spanning tree not necessarily a minimum spanning tree Is there an algorithm to find a spanning tree. I know that there are $n^{n-2}$ of them and we have algorithms to find a minimum spanning tree.

But what if I just want any spanning tree? It doesn't have to be minimum.

For a graph with no edge weights, should I just assume that the edge weights are all 1 and then use a Kruskal's or Prim's algorithm for minimum spanning tree?

Use the BFS or the DFS algorithms. They work in $O(n)$ and output a spanning tree if the input is a connected graph


How can I find $\Theta(log(m_1)+...+log(m_k))$ as related to $m$? given:
$$m_1+m_2+...+m_k=m$$
How can I find $\Theta(log(m_1)+...+log(m_k))$ as related to $m$?

I know that i can doing that: $O(log(m_1)+...log(m_k))=O(log(m)+...+log(m))=O(k \cdot log(m))$ , but can I find something without $k$ ?

The $\log$ function is concave so, by Jensen's inequality,
$$\frac{1}{k}\sum_{i=1}^k\log m_i \leq \log\Big(\frac1k\sum_{i=1}^k m_i\Big)$$
i.e.,
$$\sum_{i=1}^k \log m_i \leq k\log\frac{m}{k} = k\,(\log m - \log k)\,,$$
which is basically what you got by bounding $\log m_i\leq \log m$.  We can't do any better than this because we could have $m_1 = \dots = k_m = \tfrac{m}{k}$, in which case $\sum_i\log m_i = k\log\tfrac{m}{k}$.

However, if $k$ is a fixed constant, then $k\log\tfrac{m}{k}=O(\log m)$.


What happens when sink transition is enabled Well I guess it is only a matter of definition but I've failed to find certain answer to the following question:

In a Petri net if transition has k inputs and zero outputs what is considered to happen when transition fires? Do we have just k - 1 token left and then just transition is not enabled?

Yes. Firing the transition just consumes one token from each of its input places.


A systematic approach to creating a simple test parser I need to create a simple text parser that replaces {tokens} with text from a table. The more complicated bit is the {?text?} tag where text must be included only if the preceding AND the following tokens exist and are not empty. You could do {?text} where it looks for a non-empty neighbouring tag only on that side.

I am not a CS student and I don't have any formal education, but I am interested in this stuff.

I know I can bodge this via common sense and general logic but I would like to approach this in a more systematic manner, as this seems simple enough and like an excellent learning opportunity.

I am aware of the concept of formal languages and grammars, but I'm not sure where to start apart from randomly jumping over wikipedia pages that seem relevant(like Context-free grammars and Parse trees), until something starts making sense.

As far as I can tell, you can model this easily using any number of formalisms. Of course, if you insist on the specific syntax you have invented, you may be out of luck and may have to build your own engine.

I wouldn't to that if I were you: you have both forward and backward references, and your "data access" tokens closely resemble your "logic" tokens, so processing may become troublesome.

Consider this instead:

{if weight}; Weight is: {weight}kg{endif}

This can easily be parsed using standard techniques, and is immediately familiar to many people. It also supports nesting (if you use a context-free parser).

That all said, here is a sketch of an algorithm that will parse your syntax, assuming that there is no nesting at all (which you don't seem to specify).

We simply work in two phases:

Lex the input into tokens: regular text, and your special tokens. Represent the former by text(text) latter by two types, data(name) and conditional(left, right, text).

Go over the token list, evaluating each token according to these rules:

 eval text(t) ==> t
 eval data(n) ==> value(n)
 eval conditional(left, right, text) ==>
    if   (!left || (eval predecessor) != "")
      && (!right || (eval successor) != "") {
        text
    } else {
        ""
    }

You see that you have to keep two copies in memory, at least for a time.

I think it's straight forward to transform this solution so that you move a three-token window over the token stream; this way, you can forget old tokens, and only need to lex one token in advance. So, as long as your conditional tokens only depend on their immediate neighbours, this can be efficiently parsed.


Optimal insertion of edges for a graph I am working on a problem which could be reduced to a graph optimization problem as below.

A set of colored nodes is given.
The edges are to be inserted between the nodes.
A node can have only 4 edges at max.
A table provides rules for profit contribution from the edges.

Eg.,

An edge connecting red to red: profit is 10
An edge connecting red to blue: profit is 20

The total number of colors is typically around 20 to 30, but it can go as high as 50. Correspondingly the table for profit(edge) would be a long list but it won't list all possible combinations. The profit for edges not specified in the table is assumed zero.

The problem is to optimize the connections (edges) such that the total profit is maximized.

I am wondering if this problem, maybe in some other way, is known. If so, please provide any pointers that might be of help. Thanks.

Let your vertex set be $\{v_1, \dots, v_n\}$.  If $n\leq5$, just add all possible edges.  Otherwise, create a new graph with vertices $\big\{v_{i,j}\mid i\in\{1, \dots, n\},\ j\in\{1, 2, 3, 4\}\big\}$, and edge set $\{v_{i,j}v_{k,\ell}\mid i\neq k\}$. You're looking for a minimum-weight perfect matching in that graph.  (Which is the same thing as a maximum-weight matching in the graph where you multiply all the costs by $-1$). This can be done in polynomial time, even though the graph isn't bipartite.


Dynamic Programming Solution for Optimal Matrix Chain Multiplication Order I have been thinking about why the dynamic programming approach to finding the optimal matrix chain order is better than a brute force approach that finds the optimal order by exploring all nested orders. The more I think about it, the more I feel strongly that the dynamic programming solution considers all possible chain orders, thus contradicting the justification of choosing a dynamic programming approach to solving this problem.

For Eg. Lets consider a product of 4 matrices. There are 5 possible matrix chain orders (in the brute force method)

(A1 (A2 (A3 A4)))

(A1 ((A2 A3) A4))

((A1 A2) (A3 A4))

((A1 (A2 A3)) A4)

(((A1 A2) A3) A4)

Now, if we consider the dynamic programming approach all the sub matrix products included in each of the orders above will be computed. How then is the dynamic programming approach more efficient than the brute force approach?

EDIT: The answers and the comments have been really useful in helping me understand the DP solution better. But I am not able to visualise a brute force approach  in my head. As soon as I start writing a brute force method to compute all possible matrix multiplication orders, the DP solution manifests itself naturally in my attempt. This may be because I know the optimized DP solution and I am not able to think of a rudimentary brute force solution. If someone can mention the pseudo code for generating all possible matrix multiplication orders , it will make it clearer as to what sub-problems the DP solution avoids and hence is more efficient.

EDIT (again): Let us disregard memoization. Will the DP solution still generate lesser number of computations?

The dynamic programming solution computes a table that for each $i\le j$ has the optimal solution for $Ai$, ... $Aj$. The computation is done bottom-up, and (as one of the comments notes) many values are reused. Total complexity order $n^3$ as there is a quadratic number of $i,j$ each taking linear time to compute.

A real brute force takes exponential time, the number of binary trees, which is equal to the number of nested expressions. See Catalan numbers.


What would be a not arithmetically definable language that is not Turing reducible to another given not arithmetically definable language? I have this question I'm struggling with.

Let $A=\{<i,n>|\;n \in \phi ^{(i)}\}$. In other words, $A$ is the language defined by the set of all pairs $<i,n>$ such that $n$ is $\leq_m$ to the $i$th Turing jump.
A is definitely not an arithmetically definable language, and you can prove this by contradiction.

I have to find a language, let's say $B$, that is more complex than $A$ $i.e.$ $B\nleq_T A$. I thought about $B=\{<i,n>|\;n \not\in \phi ^{(i)}\}$, but I'm not sure about my reasoning, I think an oracle turing machine with an oracle $A$ couldn't reduce to $B$..

And one last thing, do you think there exists a language that is more complex than any other (it doesn't reduce to anything)?

If you have any hints that could help me solve those two questions I would be really grateful!

Reiterating my comment, for each $A$ we can construct a language $A'$ (read: $A$ jump) which cannot be reduced to $A$ by taking all halting TMs with oracle access to $A$. The classical proof of the undecidability of the halting problem applies, showing that $A'$ cannot be (Turing-)reduced to $A$.


How do I show that a DFA accepts only one word? I want to show that

$\qquad\displaystyle O = \{M : M \text{ is a DFA}, |L(M)| = 1\}$.

Here $|L(M)|=1$ means the DFA contains only one state. I really don't know where to get started in this problem.

Should I do something like this?

M = On input (M',w) where M' is a DFA and w is a string:

 - If M' accept only one member, accept.
 - If more than one or less than one accepted, reject.

But this will loop the program forever for the first step as it keeps testing every member after one member is selected. First step just doesn't seem right.

I think these questions might be relating to this: 1, 2

The case of 1-state DFA

Accepting one word is unrelated to having one state.

If there is only one state, it is necessarily starting and accepting
state, unless there is no accepting state which make the language empty.

An automaton that has only one state which is accepting is necessarily
accepting a language equal to $\Sigma_1^*$ for some subset $\Sigma_1$
of the input alphabet $\Sigma$.

Then the automaton accepts exactly one word if and only if it is the
empty word $\epsilon$, which is the case when $\Sigma_1=\emptyset$

Multi-state DFA

Now, assuming you can have more than one state (I would think that you
did not intend to have such a restriction).

You look at your DFA as a directed graph.

Acceptance of a word is equivalent to finding a path from initial
state to a final state. Since the automaton is deterministic there is
a bijection between such path and the words of the
language. Furthermore, the length of the word is equal to the length
of the path.

Finding one path between the initial state and a final state can be
done simply by tracing, starting with the initial state.
You start with a set $U$ (for untraced) containing only the initial
node, and a set $T$ (for traced once) initially empty.

Then for any state $q$ remaining in $U$, you add all nodes $q'$ with a
transition $q\to q'$ to $U$ unless they are already in $U\cup T$, and
you transfer $q$ from $U$ to $T$. You
terminate when $U$ is empty, and then all nodes in $T$ are reachable from
the initial state. Note that this is the gist of tracing garbage
collection algorithms. The complexity is linear if inclusion of a node
in a set is checkable in constant time (for example by marking the node).

Now, in order to check for multiple paths, you modify a bit the
algorithm, replacing $T$ by two sets $T_1$ (for traced once) and $T_2$
(for traced twice). You proceed as before, with the following changes, that depend on whether $q$ is in $T_1$ or not.

When $q\notin T_1$ ( $q$ was never traced, nor accessed from two paths), consider successively every transition $q\to q'$, making sure you process first a transition $q\to q$ if any exists:

if $q'$ is already in $T_2$, you ignore it
else, if it is in both $U$ and $T_1$, you ignore it
else, if it is in $T_1$, but not in $U$, you add it to $U$ (leaving it
in $T_1$ too).
else, if it is in $U$, but not in $T_1$, you add it to $T_1$ (leaving it
in $U$ too).
else, if $q'$ is in none of the sets, you add it to $U$.

Then you move the node/state $q$ to $T_1$ if it is not already in
$T_1$, or to $T_2$ if it is in $T_1$ (you may remove it from $T_1$ if
convenient for set encoding, but it does not matter). Note that $q$ may already be in $T_1$ if one of the transitions just processed is of the form $q\to q$.
When $q\in T_1$ (there are at least two paths to $q$), consider successively every transition $q\to q'$:

if $q'$ is already in $T_2$, you ignore it
else, put $q'$ in both in both $U$ and $T_1$ (it may be there already)

Then you move the node/state $q$ to $T_2$ (and you may remove it from $T_1$, if you wish).

When you terminate (with $U$ empty), you have at least two paths from
the initial state to a final state if and only if you have an
accepting state in $T_2$, or two accepting states in $T_1$.
You have at least one path if $T_1\cup T_2$ contains an accepting state, and no path it it does not.

So the necessary and sufficient condition for the existence of exactly a single word in the language is that there is a single accepting state in $T_1$ and none in $T_2$.

With proper encoding of the sets, this works in linear time (in the size of the DFA), and can be quite fast.

Note: the conditionals have been written for better readability. They can be better organized for efficiency.


How are Operating systems involved in execution of programs? By my understanding, operating system is the abstraction layer above hardware. Which means that an operating system that supports two different CPU architectures can run the same code. But I still cant understand the details/steps of executing a given program.

Suppose, I have a program that takes 2 numbers from the user, adds them and displays the answer. There are few steps in which the program does its work (Might be missing something or wrong somewhere, feel free to correct):

1) Double clicking the program file icon.

(a) How do the GUI and the mouse (and RAM) interact to identify which icon is
       clicked?

2) Loading of program in the Main memory using the address of the icon clicked.

(b) How is the os involved in finding that file from the disk?

3) Input of 2 numbers (CPU reads instructions of taking input from keyboard).

(c) Will the example of 2 different keyboards (For eg: one with 'fn' key like
       in laptops and one of full size) be a good example for explaining the need
       of device controllers and drivers?

4) Adding of the 2 numbers (Arithmetic operations).

(d) Is the os responsible for providing the CPU with the addresses of the
       operands and operators?

5) Displaying the output on the monitor.

I understand that the question might be broad, but I am not able to piece together all these things just by reading books (like 'Operating System Concepts by Galvin').

Also, I like as much detail as possible as it makes things more clear.

At one level you have hardware: A computer with a CPU, RAM, hard drive, graphics card, monitor, keyboard and so on.

Then on the lowest level of the operating system you have code that can talk to these devices. That code allows the operating system to read or write data from the hard drive, determine the location of the mouse, and so on.

At a higher level of the operating system, the OS has code to assign address space to processes, start processes and kill them, allow these processes indirect access to the hardware.

Above that, it is just code. You have a mouse reporting it's location, you have graphics hardware that can display a cursor, so someone wrote code that keeps track of the mouse location and displays the cursor at the point corresponding to the mouse location. And then someone wrote code to display icons. And more and more and more code on top of that. And that's all, really.


If a comparison-based algorithm finds the ith smallest element, it also classifies all the elements as ≥a[i] or ≤a[i] Suppose that an algorithm uses only comparisons to find the $i$-th smallest element in a set of $n$ elements. Show that it can also find the $i−1$ smaller elements and the $n−i$ larger elements without performing any additional comparisons.

I would like to show my solution. I ask you for checking it :)

Let $k$ will be $i$-th element.
Let's suppose that we don't know if element $x$ is larger or smaller than $k$
Then it is impossible to know if $k$ is the $i$-th element. Contradiction.

It is very short proof. I can't see reason that it is not correct.

Any comparison algorithm produces a partial order on the input (assuming all elements are distinct!). The key observation is:

  Suppose that in some partial order, some element $x$ has $\ell$ elements smaller than it. Then the partial order can be extended to a total order in which element $x$ has exactly $\ell$ elements smaller than it (i.e., it is the $(\ell+1)$st element).

Why is this enough? (The following is somewhat informal. See below for a more formal proof.) Suppose that your comparison algorithm outputs an element $x$ but knows only $j < i-1$ elements smaller than it, that is, in the corresponding partial order, only $j$ elements are smaller than $x$. Then there is some total order in which element $x$ is in position $j+1 < i$, and in particular, you cannot be sure that $x$ is the $i$th element. Similarly, if the algorithm knows only $j < n-i$ elements larger than $x$, then there is some total order in which $x$ is in position $n-j > i$ (using the dual version of the observation). Therefore the only way in which a comparison algorithm can be sure that $x$ is the $i$th element is if in the corresponding partial order, $x$ has exactly $i-1$ elements smaller than it and $n-i$ elements larger than it.

It remains to prove the observation. Given a partial order, we can generate a total order extending it by repeatedly performing the following operation:

  Choose a source (a minimal element) $y$, output it, and remove it from the partial order.

This (non-deterministic) algorithm outputs the elements in a certain order which is a total order extending the given partial order.

In order to apply this algorithm to prove the observation, consider the set of elements $P = \{ y : y \leq x \}$ which are at most $x$. In the first $\ell+1$ steps, we always choose a source from $P$ (this is always possible, though this requires an inductive argument). Then it continues in some arbitrary fashion. The resulting total order has $x$ as the $(\ell+1)$st element.

Our argument above, showing how the key observation implies the result, was somewhat informal. Here is a more formal treatment. We will actually show a slightly weaker result, that if a comparison algorithm finds the $i$th element correctly on all inputs with distinct elements, then it "knows" which elements are smaller than the $i$th element (can output them without further comparisons). The stronger result is left as an exercise to the reader.

We can think of the algorithm, when restricted to inputs with distinct elements, as a binary tree: each non-leaf compares two elements and has two children corresponding to the result of the comparison, and each leaf contains the output of the algorithm. We can furthermore assume that each vertex is reachable (we can always prune the tree to ensure this).

We can annotate each vertex with the partial order on the input elements, representing the algorithm's knowledge given the results of the preceding comparisons. We will show that at each leaf with output $x$, the corresponding partial order has exactly $i-1$ elements smaller than $x$ and $n-i$ elements larger than $x$.

The proof is by contradiction. Suppose that there is some leaf with output $x$ at which there are $j < i$ elements smaller than $x$ (the other case, of having less than $n-i$ elements larger than $x$, is handled symmetrically). The key observation shows that there is some linear order $L$ extending the partial order in which $x$ is not the $i$th element. If we had input this linear order to the algorithm, it would have reached the same leaf, and so would have answered incorrectly – contradicting our assumption that the algorithm is valid.

We conclude that at each leaf with output $x$ there are exactly $i-1$ elements smaller than $x$ and $n-i$ elements larger than $x$.


Decide whether DFA have useless states A useless state in a DFA is one that is never entered on any input string. Consider the problem of determining whether a DFA has any useless states. Formulate this problem as a language and show that it is decidable.

I know how to prove it with Turing Machines, but not DFAs. So here is my proof for TM:

Let $U_{\mathrm{TM}} = \{\left \langle M \right \rangle|M \text{ is a TM that  has a useless state}\}$. We show that $U_{\mathrm{TM}}$ is undecidable by a reduction from $\mathrm{HALT_{TM}}$ to $U_{\mathrm{TM}}$:

If $\left \langle A,w \right \rangle \in \mathrm{HALT_{TM}}$, then $A$ halts on input $w$ and $M_A$ visits all its states on every input; thus, $\left \langle M_A \right \rangle \notin U_{\mathrm{TM}}$. iIf $\left \langle A,w \right \rangle \notin \mathrm{HALT_{TM}}$, then $A$ loops on input $w$ and so does $M_A$; therefore, $M_A$ will never visit state $q_u$ and $\left \langle M_A \right \rangle \notin U_{\mathrm{TM}}$. Since $\mathrm{HALT_{TM}}$ is undecidable, $U_{\mathrm{TM}}$ is undecidable.

But for DFA I have to show that the language is DECIDABLE. Do you have any ideas how I can go with that?

In order to show decidability, you need to provide an algorithm that will always halt, and yields a yes / no answer.

The following algorithm will return if there is a useless state in a given DFA (and can return the useless state).

Given a DFA $A$, run a BFS from the initial state ($q_0$), and mark every node that is being visited.

When BFS terminate (and it will, because we're dealing with a deterministic finite automata), every state that wasn't visited during the scan is a useless state.


Why is automatically labeling data in unsupervised learning hard? I currently studying machine learning and pattern recognition area. Today, my professor said implementing an unsupervised system that automatically labels data is difficult. Why is that?

I think if I am given a data set, then I can categorize all data into groups. Then, for unknown input data, I can extract features and put it into the group that best fits all the features. Can anyone explain whats wrong with my intuition and why is it difficult problem?

The problem with your intuition is that, frankly, you don't have one. At least not a useful, that is algorithmic one, one that tells you what is hard for computers and what is not. You think in terms of what you can do with every-day data -- but that's not an appropriate frame of reference for this problem. As evidence, consider this question.

Some specific concerns:

"I can" != "I can build an algorithm which can".
Can you? Look at some data dumps from CERN and try to classify them.
What exactly are "features" (mathematically)?
What does "fits best" mean (mathematically)?

I recommend three things that will help you build a (better) intuition.

Study computability and complexity theory -- this will help you build intution for hardness of computational problems.
Program things -- this will help you build intution for hardness of implementing things.
Try to build an unsupervised learner and fall into all the pitfalls.


How does lexical analyzer remove white spaces from source file? In compiler at phase lexical analyzer, how does lexical analyze strip out white spaces from source file?.

A brief answer is "by ignoring them".
A compiler may scan the entire code more than once, but of course at least once in which case we call it a single-pass compiler. The task of lexical analyzer (or sometimes called simply scanner) is to generate tokens. This is done simply by scanning the entire code (in linear manner by loading it for example into an array) from the beginning to the end symbol-by-symbol and grouping them into tokens. Thus, while checking each symbol (of the source code) you just skip the white-space symbols. Similarly you skip comments in the source code.

As to my personal experience, I had to implement a single-pass compiler for a made-up simple language which allowed both white space symbols (TAB, NEW-LINE, SPACE) and comments. I loaded the entire source code into a linear array and as my lexical analyzer went over the code character by character it simply skipped all white space symbols and comments by moving forward the pointer pointing to the current character.

But depending on the implementation you could first pass over the source code just to remove all white spaces, and then on the second pass generate tokens.

Caution:  "ignoring whitespace" shouldn't be interpreted as "remove all white space symbols from the source and then further process the source code". In some cases depending on the language construct white spaces may indicate when a token ends for example in the following piece of code

  int foo(int x)
  {
    return x+2;
  }

The tokens TYPE (int) and the IDENTIFIER (foo) are separated by a single SPACE. But the IDENTIFIER (foo) and immediate LEFTPAR are not separated by any white space symbol.

Also (on Derek Elkins' comment) real compilers usually use whitespace for producing clear error messages, for example for keeping track of line numbers.


Proving that directed graph diagnosis is NP-hard I have a homework assignment that I've been bashing my head against for some time, and I'd appreciate any hints. It is about choosing a known problem, the NP-completeness of which is proven, and constructing a reduction from that problem to the following problem I'll call DGD (directed graph diagnosis).
Problem

An instance of DGD $(V,E,k)$ consist of vertices $V = I \overset{.}{\cup} O \overset{.}{\cup} B$, directed edges $E$ and a positive integer $k$. There are three types of vertices: vertices with only incoming edges $I$, vertices with only outgoing edges $O$ and vertices with both incoming and outgoing edges $B$. Let furthermore $D=O\times I$.
Now, the problem is whether we can cover all nodes with at most $k$ elements of $D$, i.e.
$\qquad \displaystyle \exists\,S\subseteq D, |S|\leq k.\ \forall\, v\in V.\ \exists\,(v_1,v_2) \in S.\ v_1 \to^* v \to^* v_2 $
where $a\to^* b$ means that there is a directed path from $a$ to $b$.

I think that the Dominating Set problem is the one I should be reducing from, because this too is concerned about covering a subset of nodes with another subset. I tried creating a DGD instance by first creating two nodes for each element of the dominating set, copying all edges, and then setting the $k$ of the DGD instance equal to that of the DS instance.
Suppose a simple DS-instance with nodes $1$, $2$ and $3$ and edges $(1,2)$ and $(1,3)$. This is a yes-instance with $k = 1$; the dominating set in this case consists of only node $1$. Reducing with the method just described, this would lead to a DGD instance with two paths $(1 \to 2 \to 1')$ and $(1 \to 3 \to 1')$; to cover all nodes, just one pair $(1, 1')$ would be sufficient. This would have worked perfectly, were it not for the fact that the dominating set of the DS-instance cannot, of course, be determined in polynomial time, which is a requirement here.
I have found that there are many good-looking ways to transform the edges and vertices when reducing, but my problem is somehow expressing DGD's $k$ in terms of DS's $k$. Dominating Set seemed a fitting problem to reduce from, but because of this I think that maybe I should try to reduce from a problem that has no such $k$?

Reduce from NP-complete SET-COVER instead.

Let $S_1,\dots,S_m \subseteq\{1,\dots,n\}$ with $k\in\mathbb{N}$ an instance of set cover. Define an instance $(V,E,k')$ of DGD like this:

$V= \{s_1,\dots,s_m,o_1,\dots,o_m,e_1,\dots,e_n,o\}$
$E= \{(s_i,o_i) \mid i = 1,\dots,n \} \cup \{(s_i,e_j)\mid j \in S_i\} \cup\{(e_j,o)\mid j=1,\dots,n\}$
$k' = m + k$

It is easy to see that the constructed DGD instance has a positive answer if and only if the given set cover instance has a positive answer. In particular, all $m$ pairs $(s_i,o_i)$ have to be chosen no matter what in order to cover all $o_i$; then $k$ of the $m$ pairs $(s_i,o)$ have to cover all the $e_j$, and the first components of those chosen are the solution of the SET-COVER instance. If no such choice is possible the SET-COVER instance has no solution as well.

As the construction is possible in polynomial time, this proves SET-COVER $\leq_p$ DGD.

As an example,consider the example set cover instance given on Wikipedia, namely $\{1,2,3,4,5\}$ and sets $S=\{\{1,2,3\},\{2,4\},\{3,4\},\{4,5\}\}$. This translates to the following graph:

[source]


Akra-Bazzi method integral diverges I want to solve this recursion:

$$T(n) = 5T(\frac{n}{5}) + \frac{n}{lg(n)}$$

My attempt and issue:

None of the cases for master theorem apply here.
I tried using Akra-Bazzi method (https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method) with

$f(n) = \frac{n}{lg(n)}$

The derivative of $f(n)$ satisfies the condition for Akra-Bazzi:
$$\frac{d}{dn} f(n) = \frac{1}{lg(n)} - \frac{1}{ln(2)*lg^2(n)} = O(n)$$
Also I found that $p=1$ to satisfy the method's condition that $\frac{a}{b^p} = 1$.

Now the solution is given by this formula:

$$T(n) = \theta(n^p*(1-\int_{1}^{n} \frac{f(x)}{x^{p+1}} dx)$$

So  I calculated the integral:
$$\int\frac{f(x)}{x^{p+1}} dx = lg(lg(x)) + C$$, but with one of the limits being $1$ it diverges!

The weird thing is that according to Wolfram Alpha calculator, $T(n) = \theta(nlg(lg(n)))$.

So why is it true if the integral diverges? What am I getting wrong here?

Your recurrence isn't really defined for $n = 1$. This suggests using a different value for the lower bound in the integral. The formula given by Akra–Bazzi doesn't actually depend on the exact value of the lower bound that you choose – it can at most affect the big Theta constant or, in your case, some lower order term. If you choose any lower bound which is large enough, then the Akra–Bazzi formula gives you $\Theta(n\log\log n)$ as wanted.


How do nondeterministic Turing machines compute general function problems? (Hope this hasn't been asked before, but I didn't find anything.)

In my understanding, nondeterminism applies to decision problems only, due to the requirement of the existence of an accepting path. In Wikipedia, the class $NP$-easy is defined to be solvable in deterministic poltime, with access to an oracle for a decision problem in NP. So this seems to back my assumption.

My question is: Is there an accepted way to define a non-deterministic Turing machine to compute a general function problem? (And is it always by a detour over an oracle for a decision problem?)

One accepted definition is as follows: a function $f$ (whose output is at most polynomial in its input) is in the class $\mathsf{FNP}$ if given $x,y$ one can decide in polynomial time whether $f(x)=y$. Compare this to the class $\mathsf{FP}$, which contains those functions $f$ such that given $x$, the value of $f(x)$ can be computed in polynomial time.


The constant in the merge sort recurrence Assuming that the worst case running time of merge sort can be described with this recurrence:

$\
T(n) =
\begin{cases}
  \theta(1) & \text{if }n = 1\\
  2T(\frac{n}{2}) + \theta(n) & \text{if } n\gt 1
\end{cases}
$

Introduction to Algorithms says that it is possible for the same constant $\ c $ to represent the time required to solve problems of size $\ 1 $ as well as the time per array element of the divide and combine steps, so that

$\
T(n) =
\begin{cases}
  c & \text{if }n = 1\\
  2T(\frac{n}{2}) + cn & \text{if } n\gt 1
\end{cases}
$

How is there a constant $\ c $ that can represent both times? Shouldn't the proper way to describe the recurrence be

$\
T(n) =
\begin{cases}
  a & \text{if }n = 1\\
  2T(\frac{n}{2}) + bn & \text{if } n\gt 1
\end{cases} \text{where }a\ll b
$

If the answer is dependent on the psuedocode provided in the book, I'll post it here. However, there is a single if statement in a trivial mergesort (size 1). Surely, the cost of that single if statement can't be the same as the sum of the costs of all the steps taken in the merge step, as well as the constant-time division of the problem into smaller problems?

Sorry if this has been asked before.

Nitpick: Are they really talking about time? If they are actually counting some operation, it's well possible (if unlikely) for the same constant to show up in both places.

  How is there a constant  c that can represent both times?

It (probably) can not. This is a simplification done with the goal in mind: derive a $\Theta$-bound.

Apply the Master theorem to both candidate recurrences; you'll note that the result stays the same. CLRS know this from experience, so they simplify the recurrence a-priori.


Fixed size set to contain the maximum number of given sets I asked this question in SO here

I have about 1000 sets of size <=5 containing numbers 1 to 100.

{1}, {4}, {1,3}, {3,5,6}, {4,5,6,7}, {5,25,42,67,100} ...

Is it possible to find a set of size 20 that contains the maximum number of given sets?

In other words, let $U = \{1, 2, ..., 100\}$ and $S \subseteq \{Z \in 2^U \mid |Z| \leq 5\}$. How can I find $X \subseteq U$ with $|X| = 20$ such that $|\{Y \in S \mid Y \subseteq X\}|$ is maximized?

Checking each of 100!/(80!*20!) sets  or bulding all set combinations with size <=20 is inefficient.

Is there any (semi)efficient solution or is it np-complete?

The set {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20} contains 5 sets.

The decision version of the problem can be formulated as follows:

Given a collection of sets of numbers $S$. Each number is drawn from a set $U$.
You want to know if there is a way to pick $k$ numbers from $U$ to form a set $X$ which is the superset of $s$ sets in $S$.

The following is a reduction from k-clique which is an NP-complete problem.

The k-clique problem has an input as a graph and asks if there is a way to pick $k$ nodes so that there is an edge between any two of the $k$ nodes.

We turn each node into a number. These numbers form the set $U$. We turn each edge into a set containing two numbers representing the corresponding two nodes of the edge. These sets form the set $S$.

The question to the original problem is: Is there a way to pick $k$ numbers from $U$ to form a set $X$ such that $X$ is the superset of $C_{2}^k$ sets in $S$

The proof has two directions.

If there is a k-clique in the graph, then we can pick the $k$ numbers corresponding to $k$ nodes in the clique to form $X$. Because of the way we transform the graph, we know there will be $C_{2}^k$ sets in $S$ each corresponds to an edge in the original graph and thus is a subset of $X$. So the answer to the original problem is positive.
If there is no clique of size $k$, then for any set of $k$ nodes chosen from the graph one can only have less than $C_{2}^k$ undirected edges between any two picked nodes. Otherwise, we will have a clique of size $k$. This means that there can only be less than $C_{2}^k$ subsets of $S$ which is a subset of the set $X$ formed by any $k$ chosen numbers. So the answer to the original problem is not positive.

The transformation is in poly-time. The reduction is proven, so the problem is NP-hard.
The problem is clearly in NP because we check how many sets covered by $k$ numbers in poly time. This means the original problem is NP-complete.


Fibonacci Series with Dynamic Programming We can compute Fibonacci numbers by means of dynamic programming approach. If we do not store intermediate solutions, we cannot use them for future necessities. In this case, asymptotic complexity reaches exponential time.

             f(5)    -> 2^0
            /    \
           /      \
          f(4)    f(3)   -> 2^1
         /   \    /   \
       f(3) f(2) f(2) f(1) ->2^2
      /   \
     f(2)f(1)............

Each recursive call consumes only O(1) time.

T(n) = 2^0 + 2^1 + 2^2.... (geometri series)

T(n) = (2^n - 1) / 2 - 1

T(n) = O(2^n)

In some places, it is written that n is size of the problem, but I think n is number of levels in recursion tree. Is n equal to size of the problem or number of recursion levels ?

$n$ is the index of the Fibonacci number you're computing. For example, the sixth Fibonacci number, $f(6)$, is equal to 8.

If we assume that function calls take constant time and we are using your model, then it's clear that the number of calls, $C(n)$, to compute the $n$-th Fib will be given by
$$C(n)=C(n-1)+C(n-2)$$
with $C(0)$ and $C(1)$ both being 1.

Hmm. That recurrence is almost exactly the recurrence for the Fibs, just shifted by a place, so we have $C(n)=f(n+1)$. In other words, the asymptotic growth of $C(n)$ is the same as the Fibs themselves.


Finding path with specific length in weighted graph Given a weighted, cyclic, directed graph and two nodes I am looking for a connecting path which total weight comes as near as possible to a specific value which is greater than the shortest path.
Example in a real world scenario: Find a route from Washington D.C. to New York City which is 400 miles long, despite the shortest path is ~230 miles. All my considerations so far failed for one of the following reasons:

Most routing algorithms like Dijkstra are not working in this case because there is nothing to minimize or maximize (the divergence of given weight to path weight should be minimized, but you need the finished path to calculate it)
DFS and BFS can be used to find a path with a specific number of hops (edges), but it doesn't consider weighted edges

EDIT:
Cycles are forbidden to avoid the simple solution shortest path + cycles until distance is reached. The algorithm doesn't have to find the optimal solution, a route with length in a given threshold is acceptable.

Your problem is NP-complete by a reduction from Hamiltonian $st$-path, even with unweighted arcs. Thus, you should not expect a polynomial-time algorithm. I'll sketch a reduction below.

Let $G$ be an instance of Hamiltonian $st$-path with all $m$ arcs having weight 1. Let $G'$ be a graph obtained from $G$ by adding a long directed path of length $C$ starting from $t$ ending at (say) $t'$. Now, if there's an Hamiltonian path from $s$ to $t$, there is also a path from $s$ to $t'$ of length $m$ plus $C$. On the other hand, if there's a path of length $m+C$ from $s$ to $t'$ in $G'$, you can chop off the long path from $t$ to $t'$ to obtain a Hamiltonian $st$-path in $G$.


Proving Irregularity of $L = \{ a^mb^nb^n \mid nm \ge 3 \} $ I'm trying to prove the irregularity of the following language:
$$L = \{ a^mb^nb^n \mid nm \ge 3 \} $$
I tried to demonstrate that it doesn't verifies the Pumping Lemma but for all words I tried it seems to accept all of them.
Any hints or suggestions?

It is regular since $a^*(bb)^* \setminus L$ is regular:
$a^*(bb)^*\setminus L = a^* \cup (bb)^* \cup \{a^mb^{2n}|1\leq mn < 3\}$
The last language of the union is finite thus regular.


Why is this language Turing recognizable and not not-Turing recognizable I read that the following language is r.e. but not not-Turing recognizable
$L$: On input $M$ (where $M$ is a Turing Machine), $M$ accepts at least 20 inputs
I am not sure why it is not not-Turing recognizable., since I could perhaps make the following reduction from $\overline{A_{TM}}$ to $L$ given this procedure $R$ namely:

$R$: On input $<M,w>$:

Construct TM $M_1$, where on input $x$, if $x=1$, accept
If input $x$ is not equal to $1$, run $M$ on input $w$ for $|x|$ steps. If after $|x|$ steps, $M$ does not accept $w$, then accept $x$

From this reduction, if $M$ does not accept $w$, i.e. $<M,w> \in \overline{A_{TM}}$, then $M_1$ accepts any input word, i.e. $M_1 \in L$.
Am I missing something here?

What you are missing is that if $\langle M, w\rangle \notin \overline{A_{\mathrm{TM}}}$, i.e. if $M$ halts on input $w$, you don't know whether or $M_1 \notin L$. If $M$ does halt on $w$, but this takes longer than $20$ steps, it would also hold that $M_1 \in L$. Thus, you don't have a reduction here.
That the language $L$ cannot be co-RE is an immediate consequence of Rice's theorem.


Address and data bus When people use the word "bidirectional" while describing buses, what are the two "directions" that are being talked about?

Also, why is the address bus unidirectional, as opposed to the data bus?

Edit: If all these buses are just connecting wires, what is the meaning of a 16 bit address bus? Does it mean that the wire can carry 16bits of information at a time?

Buses usually connect the central processing unit (CPU) with peripheral devices, like memory or other Input/Output devices.

To activate a memory you need to do two things:
- specify the cell in the memory you want to write to / read from  (that would be the address)
- give the data to write to the memory, or take the data from the memory (this information would go over the data bus)
- control the memory: tell the memory if this is a read or a write, etc.

So as you can see, in both READ and WRITE you must specify the address you want to write to, or to read from. So the address bus is uni-directional: from the CPU to the MEMORY.

The information itself goes in both directions. In a READ it goes from the memory to the CPU, and in a WRITE it goes from the CPU to the memory. Hence, the data bus is bi-directional.

The control bus is usually uni-directional: the CPU is the master and the peripherals are slaves. "Controlling" in the other direction goes via the interrupts mechanism.

Finally, as you mention, buses are just connected wires. 16bit means that there are 16 wires connected in parallel. So an address bus of 16bits can specify any address between 0 (=16 times 0) to $2^{16}-1=65535$ (=16 times 1). The data bus is capable of carrying 16bit of information, etc.


What ML methods exist to categorize signal from noise? Red noise? Spatially correlated noise? Let's say we are given measurements of some sort.

In many cases, it is safe to assume that noise is white noise, serially uncorrelated, and zero mean with some finite variance.

But in other cases, "red noise" exists such that the noise is correlated in time. What does one do in this case? Perhaps a Gaussian Process could be used?

What methods exist to characterize spatially-correlated noise?

The basic approach is to model the noise as an appropriate stochastic process (aka random process).  There's an entire subfield of statistics that has studied different kinds of stochastic processes, and they each have different properties.  It would be too much to try to summarize that entire subfield in a single answer here.


3-SAT problem with number of clauses equal to number of variables Consider the 3-SAT problem where the formula is in conjunctive normal form and we restrict the Boolean formulas such that the number of clauses in the formula is equal to the number of variables. Is this problem still NP-hard?

For example, this formula has $3$ variables and has $3$ clauses $(\lnot x_1 \vee \lnot x_2 \vee \lnot x_3 ) \wedge (\lnot x_1 \vee \lnot x_3) \wedge (\lnot x_2 \vee \lnot x_3)$,

and the following formula has three variables but has only two clauses $(\lnot x_1 \vee \lnot x_2 \vee \lnot x_3  ) \wedge (\lnot x_2 \vee \lnot x_3)$.

Let the variant of the 3-SAT problem you describe be called EQUAL-3-SAT, where (following your definition) each clause has at most 3 literals. We prove EQUAL-3-SAT is NP-complete by a reduction from 3-SAT as follows.

Let $\phi$ be an instance of 3-SAT with $n$ variables and $m$ clauses. If $\phi$ is balanced already in the beginning (the case $n=m$), we do nothing. If $n > m$, we introduce a fresh variable $x$ that does not appear anywhere in $\phi$ and add to $\phi$ exactly $n-m+1$ clauses of the form $(x)$, so we have $n=m$, and we are done.

Then, if $n < m$, we can do similar balancing: each addition of a 3-literal clause $(a \vee b \vee c)$, where $a$, $b$ and $c$ are fresh variables, increases $n$ by $3$, and $m$ by $1$. Keep adding this clause to $\phi$ until $n=m$, or the difference between $n$ and $m$ is exactly one or three (if the difference was two, repeating the process once more would balance $\phi$). If the difference is one, adding one more 3-literal clause causes $n=m+1$ thus we use the balancing process of the first step (case $n > m$). If the difference is three, we simply add an 2-clause of the form $(a \vee b)$, increasing $n$ by two and $m$ by one, again giving us $n=m$.

Finally, we observe the new formula is satisfiable if and only if $\phi$ was.


How to use a CFG to restrict a subset of a*b*c*d* so that there are at most as many a's and b's as d's? Give Context-free Grammar for the language $\{a^i b^j c^k d^h \mid i,j,h \ge 0, k>0, i+j \le h\}$

This is a training exercise, for which we don't get any answers, in a course I'm taking. I have found similar examples, but nothing that touches on the i+j≤h part of this. My biggest trouble is that it is ordered, so I have no idea how to add d's to the end when I add a's or b's to the front. I haven't gotten very far because of this, but my thinking looks like this at the moment:

S→ABcCD
A→aA | ϵ
B→bB | ϵ
C→cC | ϵ
D→dD | ϵ

I can't put things like A→aAd or A→aBCD because that would result in c's and d's before b's in the end word/string. My conclusion is that I am probably on the wrong track, but all examples I find use some sort of partitioning like this.

So could anyone point me in the right direction?

There are lots of answers on this site about this subject. See, for example here and here. The underlying idea that often works for problems like this is to work from the inside out.

The $c^k$ part is easy: just use the production $V\rightarrow cV\mid c$.
The part surrounding the $c^k$ part consists of a bunch of $b$s followed by an equal number of $d$s. That's also easy; it can be generated by $U\rightarrow bUd$. Once we're finished with that, we switch to the $c$ part, so we have $U\rightarrow bUd\mid V$.
Keep going. Now you want to surround that part with a bunch of $a$s followed by the same number of $d$s. With what we've done so far, you should be able to do this part.
Finally, we want $i+j\le h$ so we concatenate the strings we've generated so far with zero or more extra $d$s. See hint (1).

As with many subjects, it gets easier the more examples you've done. Just keep at it.


Paired resolution and $\mathsf{NP}$ vs. $\mathsf{coNP}$? Let we resolve only two clauses at time and then get rid of them. Such resolution clearly takes $O(n)$ steps.

Sequence is a set of instructions in the form $(C_{S_1}\cup C_{S_2},v\cup\overline v),...$, where $S_i$ denotes a set of merged clauses, $v\in C_{S_1},\overline v\in C_{S_2}$.

Of course such resolution taken deterministically or randomly is wrong with high probability.

For example, let's consider $\varphi=(x\oplus y)(x\oplus z)(y\oplus z)$.

Clearly this formula is unsatisfiable. But what can I get using resolution:

$(x\oplus y)\Leftrightarrow(x\lor y)\land(\overline x\lor\overline y)$.

Resolving $x$ and $\overline x$: $(y\lor\overline y)=1$.

Doing this for other clauses gives us tautology.

So, this means, that sequence $(C_1\cup C_2,x\cup \overline x),(C_3\cup C_4,x\cup \overline x),(C_5\cup C_6,y\cup \overline y)$ is wrong.

But there is a correct sequence:$(C_1\cup C_4,x\cup\overline x),(C_2\cup C_3,\overline x\cup x),(C_{\{1,4\}}\cup C_5,\overline z\cup z),(C_{\{2,3\}}\cup C_6,z\cup\overline z),(C_{\{\{1,4\},5\}}\cup C_{\{\{2,3\},6\}},y\cup\overline y)$

Showing this:

Initial formula: $(x\lor y)(\overline x\lor\overline y)(x\lor z)(\overline x\lor\overline z)(y\lor z)(\overline y\lor\overline z)$

$(x\lor y)(\overline x\lor\overline z)\mapsto(y\lor\overline z)$
$(\overline x\lor\overline y)(x\lor z)\mapsto(\overline y\lor z)$
$(y\lor\overline z)(y\lor z)\mapsto y$
$(\overline y\lor z)(\overline y\lor\overline z)\mapsto\overline y$
$y\land\overline y\mapsto0$

There are exponentially many sequences for any formula. Same applies for number of possible assignments.

But what I'm asking: is such type of resolution is proved not to be refutation-complete? In other words have someone proved that not every unsatisfiable formula has a sequence that results in empty clause? Or is it an open question? (Otherwise we'd know that $\mathsf{NP=coNP}$)

P.S. This type of resolution is sound, so only thing that I do not know is refutation-completeness.

It is known that some formulas require exponentially long Resolution proofs. Therefore Resolution cannot be used (directly) to prove that $\mathsf{NP}=\mathsf{coNP}$.

Note that the details of your procedure are completely irrelevant. The lower bounds show that whatever algorithm you use to create your Resolution refutations, there will be some formulas on which it will take exponential time, simply because every Resolution refutation of these formulas is exponentially long.


turing machine decidability proof An exercise problem once again has me stumped on a Turing Machine decidability proof.

We are given an alphabet with the strings 0 through 9.

Along with this, we have x as the infinite string of all digits in PI. (3141592...)

With L ⊆ Σ*, the language L = {A ∈ Σ*| A is a sub-sequence of x}.
(from what I understand, the definition here of a sub-sequence is  having a $x = x_1x_2x_3... $ where each $x_i$ can be constructed from Σ, then a sub-sequence of x is a finite string of the form $x_{i1}x_{i2}x_{i3} ... x_{ik}$ where $i_1 < i_2 < i_3 < ... < i_k.$

Other than that I have no idea where to start with this...

Thanks in advance.

Can you come up with a Turing machine that writes the decimal expansion of $\pi$ to tape?
Can you come up with a Turing machine that, given a string,
a separator, and the decimal expansion of $\pi$ on the tape,
determines whether the string occurs as a subsequence of $\pi$? (see this question).
Given such machines, can you 'weave' them into a single machine?


Is 95% of code really non-semantic fluff? According to A Study of Wheat and Chaff in Source Code, 95% of code is "chaff", or "non-core functionality", whatever that means. Is this really a sensible study? Does the IT World article correctly represent the original paper? It's hard to believe 95% of the code I write is "non-core". Maybe an example would help.

The original paper is A Study of “Wheat” and “Chaff” in Source Code by Martin Velez, Dong Qiu, You Zhou, Earl T. Barr and Zhendong Su.

First, note the IT World article grossly simplifies the paper. (This is partly inevitable — if you could summarize the paper in a few accessible paragraph, it wouldn't be a research paper). The 5% figure comes from a particular measure, but the paper considers multiple measures. That being said, I don't think the measures considered in the paper are particularly appropriate.

Let me summarize my understanding of the paper (I've skimmed it, I haven't read it in detail, so I may have made some mistakes or missed important points).

The paper seeks to measure the information density in source code. More precisely, they divide the source code into meaningful units (methods in Java), and they quantify how methods differ from each other, the idea being that if two methods aren't seen to differ then having those two methods instead of just one is content-free overhead (“chaff”).

To extract meaning from source code, they erase distinctions that they consider meaningless. They cut the code of a method into words (which they choose to be lexer tokens), then apply an abstraction function $a$ to each word (in other words, they consider words modulo an equivalence relation: $u \equiv v$ iff $a(u) = a(v)$). The abstraction function is the lexicon. I'll call the set of abstractions of the words in a method ($A(u_1\dots u_n) = \{a(u_i) \mid i \in [1,n]\}$ where $u_1 \ldots u_n$ are the tokens of a method) its abstraction set.

The choice of lexicon is crucial to the measure. At one extreme, you could stick all tokens into the same equivalence class ($\forall u, a(u) = \top$), and then every non-empty method would have the same minset. At another extreme, you could put all tokens in a separate equivalence class ($\forall u, a(u) = u$), and then the minset of a method would only ignore whitespace, comments, the amount of repetition of each token, and the order of token.

The minset of a method in a corpus captures how its set of words differ. A corpus is a set of abstraction sets for all the methods of a set of programs. The minset of a set $S$ in a corpus $C$ is a subset of $S$ (i.e. a subset of the set of words in a method) is a subset $S^* \subseteq S$ such that $S^*$ is not a subset of another element of $C$, and which is maximal under these constraints. Intuitively, anything you add to the minset will not help to distinguish that set from other elements of the corpus.

The 5% figure comes from a fine-grained lexicon where the equivalence between tokens is the trivial one ($u \equiv v$ iff $u = v$). The conclusion is that methods in a typical program are 95% similar.

I don't think the conclusions are particularly relevant for several reasons. The minset measure has major flaws.

If a corpus consists of a single method, then if I understand the definition correctly, its minset will be a singleton (it could be any element, the minset computation is non-deterministic). This shows that there is the correlation between the size of the minset and the complexity of the semantics that the code implements is dependent on the corpus. In order to be meaningful, the corpus has to include all the programs that one would possibly want to write, not just all the programs that were uploaded to a particular repository.

As seen above, the minset measure is also very sensitive to the choice of words and abstraction. To give an extreme example, consider binary code split into bytes, or Turing tarpit languages with a minimal set of primitives and no variables. These will have a very small lexicon, but the ways in which the primitives are combined are highly relevant to the semantics of the program. Even if we don't get into “exotic” languages, consider something like numerical code (built on top of a couple of dozen primitives like add, multiple, while, …), or symbolic processing (built on top of a few primitives like let-rec, cons, fold, …). These tend to express a lot of different behavior by combining a few primitives in rich way. The order and structure of the arrangement of primitives matters a lot, the semantics of a program is not given by the mere set of primitives that it uses.

The paper fundamentally lacks any justification for calling information that isn't captured in the minset “non-semantic” or “chaff”. Their analysis is very sensitive to language syntax and the intuitions are clearly wrong in common examples. The conclusion in the ITworld article is chosen for being sensational, not because it's a realistic measure of the semantic content of code.


Difference between graph-partitioning and graph-coarsening What is the difference between graph-partitioning and graph-coarsening with respect to scale-free networks? I am trying to analyze graphs generated using the data from social networks. Do both the terms mean the same or are they different?

They are different because... :

Graph Partitioning:

Giving a graph $G=(V,E)$, it is possible to partition $G$ into smaller components with specific properties.
e.g. the k-way graph partitioning is the problem to divide the vertex set $V$ into $k$ disjoint partition $P_1, P_2,...,P_k$ such that the number of the edges $e = (u,v) \in E, s.t. u \in P_i , v \in P_j, i \neq j $ is minimum.

Graph Coarsening:

Graph Coarsening is the first phase of a Multi-level Method, a method that partitions a graph applying one or more stage. Usually the first phase is the Graph Coarsening. This works by collapsing pairs of nodes and edges using a determinate criteria. Graph Coarsening takes as input a graph $G$ and gives as output a smaller graph $G^{'}$.
We use the Graph Coarsening because  the size of the graphs may be too big to be partitioned using well known algorithms (i.e. FM, KL) in an acceptable time.  e.g. METIS uses multi-level methods and, in this Coarsening Phase, merges pairs of nodes having a matching.

In your analysis you can use Graph Partitioning Software (METIS, Chaco, etc) in order to divide you graph and (for example) put each partition on a different node and doing distributed computing.


Depth of any node x in Weighted Quick-Union Algorithm I know from Sedgewick's book on algorithms that the max depth of any node x from a set of N nodes is at most log2(N) applying the algorithm(which says to put the shorter tree beneath to avoid tall trees) and he gives an understandable proof by induction. The thing is that I have trouble visualising that result apart form the mathematical manipulations, I mean besides proving that that assumption is correct my question is how do you get to that assumption.
This are some remarks he makes before the proof:

1)The depth of the node x increases by one when merged to another tree

2)When the depth increases the size of the tree at least doubles.

But here is the thing, he says : "The size of the tree containing x can double at most log2N times" And I don't understand why.

Here is the link to a presentation he gave on the topic. http://algs4.cs.princeton.edu/lectures/15UnionFind-2x2.pdf the proof's sketch is on slide 33.

Thanks :)

If the size of a tree starts at 1 and doubles $i$ times, it will be $2^i$ (at least -- there might be other size increases as well). If $i>\log_2N$ this would give a size $>N$ -- more than the total number of nodes.


Total ordering of sets of fixed size I'm curious if there is a name for this way of ordering finite sets of natural numbers (shown here for the case 3 elements, but can be extended to any number of them):

{0, 1, 2} < {0, 1, 3}
          < {0, 2, 3}
          < {1, 2, 3}
          < {0, 1, 4}
          < {0, 2, 4}
          < {1, 2, 4}
          < {0, 3, 4}
          < {1, 3, 4}
          < {2, 3, 4}
          < {0, 1, 5}
          < ...

The sets are generated recursively: increase the highest number and reset all the other elements to the lowest possible numbers, then apply this algorithm recursively to the remaining numbers.

The position within this ordering is given by:

C(x[1], 1) + C(x[2], 2) + C(x[3], 3) + ...

where x[i] is the i-th element in the sorted set and C(n, k) is the binomial coefficient.

Does anyone know of a name for this kind of total ordering?  Furthermore, what other common ways are there to order sets containing a fixed number of totally ordered elements?

This is just lexicographical order, but left to right (not right to left as usual).


Regular expression for capturing a "C-style" string I have started to learn automata theory and languages. I am new to regular expressions.

As a use case in real world, I would like to construct a regular expression to accept a c-style string: enclosed by double quotes, allows escape sequences (\" to escape a double quote, \ escape a backslash, \n escape a new line...) and allows all characters in between, and pretty much everything that the standard identifies as a string literal.

I don't have a specific language that the regex is to be used in, for I'm not going to use this in a program. I just want to know the theory behind constructing the regex, one step at a time. For example, Initially, how to account for the enclosing quotes ? then how to allow arbitrary sequences of characters between the quotes ? and then how to account for escaping ?

I don't have a regex tester. I just need the construction idea.

Strings that are to be accepted are, for example,

"hello world!"
"hi!\n"
"000022lkjads\t{"
"\0Hello World"

The following would be rejected

"hello

for there is no enclosing double quotes

"Hello World""

for it does not escape the quote

Here is a regular expression for the set of all strings of the following form:

They start and end with ".
Every " in the middle must be escaped using a backslash.
Every backslash must be followed by a letter from $A$.
All other letters are from $B$; in particular, " is not in $B$.

For simplicity, I identify $A$ and $B$ with the regular expressions $\sum_{\sigma \in A} \sigma$ and $\sum_{\tau \in B} \tau$.

Here is the regular expression:
$$
\text"(B+\backslash A)^*\text"
$$


In the beginning, computable functions were always total, but when where the partial functions included The modern definition of computable functions $f\colon \mathbb N \to \mathbb N$ as given on Wikipedia quite naturally describes partial functions, and not just total functions. Now I am reading some historical references, and before and around the 1930's people just seemed to be concerned with total computable function, so that when they talk about computable functions they always mean total functions.
As an example let me cite An unsolvable problem of elementary number theory by A. Church, here he just considers total functions right from the start, and when he introduces $\lambda$-definable, or recursive functions, he also just considers total function.
So at what point, and why, people dropped the assumption that computable functions always have to be total?

The Stanford Encyclopaedia of Philosophy has a summary of the history of recursive functions. In particular, in Section 1.8 we can read that Stephen Kleene explicitly defined the partial recursive functions, and showed them to be equivalent to several other notions of computable functions, in a series of papers between 1936 and 1954. For example, already his 1936 paper General recursive functions and natural numbers introduces the unbounded search operator which leads to partial functions (when the search does not find anything).


Subset sum problem with many divisibility conditions Let $S$ be a set of natural numbers. We consider $S$ under the divisibility partial order, i.e. $s_1 \leq s_2 \iff s_1 \mid s_2$. Let

$\qquad \displaystyle \alpha(S) = \max \{|V| \mid V\subseteq S, V$ an antichain$\}$.

If we consider the subset sum problem where the multiset of numbers are in $S$ ,  what can we say about about the complexity of the problem related to $\alpha(S)$? It is simple to see if $\alpha(S)=1$, then the problem is easy. Note it is easy even for the harder knapsack problem when $\alpha(S)=1$$\dagger$.

$\dagger$ Solving sequential knapsack problems by M. Hartmann and T. Olmstead (1993)

This problem can be solved in polynomial time using linear programming, and this is actually true for any partial order $(S,\le)$. By the way, we can prove by induction that for any finite partial order set  $(S,\le)$, there exists a finite set $S'\subseteq\mathbb{N}$ and a bijection $f:S\rightarrow S'$, such that for all $s_1,s_2\in S, s_1\le s_2 \Leftrightarrow f(s_1) | f(s_2)$.

Let $\mathcal{C}$ be the set formed by the chains in $S$. Remind that $C$ is a chain iff for all $v,v'$ in $C$, $v\le v'$ or $v'\le v$

Now create a boolean variable $x_v$ for each $v\in S$, and a boolean variable $y_C$ for each chain $C$. We can write the following linear program $(P)$ for our problem :
$$
\begin{split}
\text{Max} \displaystyle\sum\limits_{v\in S} x_v \\
\text{subject to} \displaystyle\sum\limits_{v\in C} &x_v \le 1, \forall C\in\mathcal{C}\\
                                         &x_v \in \{0,1\}, v\in S
\end{split}
$$

and its dual $(D)$  :

$$
\begin{split}
\text{Min} \displaystyle\sum\limits_{C\in \mathcal{C}} y_C\\
\text{subject to} \displaystyle\sum\limits_{C:v\in C} &y_C \ge 1, \forall v\in S\\
                                         &y_C \in \{0,1\}, C\in \mathcal{C}
\end{split}
$$

Then the problem of finding the minimum cover of an ordered set by chains is the dual of our problem. Dilworth's theorem states that

There exists an antichain A, and a partition of the order into a family P of chains, such that the number of chains in the partition equals the cardinality of A

which means that the optimal solution of these two problems match : $Opt(P)=Opt(D)$

Let $(P^*)$ (resp. $(D^*)$) be the relaxation of $(P)$ (resp. $(D)$) i.e. the same linear program where all constraints $x_v\in\{0,1\}$ (resp. $y_C\in\{0,1\}$) are replaced by $x_v\in [0,1]$ (resp. $y_C\in [0,1]$). Let $Opt(P^*)$ and $Opt(D^*)$ be their optimal solutions. Since $\{0,1\}\subseteq [0,1]$ we have :
$$
Opt(P)\le Opt(P^*) \text{ and } Opt(D^*)\le Opt(D)
$$
and weak duality theorem establishes that $Opt(P^*)\le Opt(D^*)$ then by putting everything together we have :
$$
Opt(P)= Opt(P^*)=Opt(D^*)=Opt(D)
$$

Then, using Ellipsoid method, we can compute $Opt(P^*)$ ( $=Opt(P)$) in polynomial time. There are an exponential number of constraints but there exists a polynomial time separation oracle. Indeed given a solution $X$, we can enumerate all couples $s_1,s_2\in X$ and check if $s_1\le s_2$ or $s_2\le s_1$, and therefore decide in polynomial time whether $X$ is feasible or otherwise the constraint associated to the chain $\{v_1,v_2\}$ is violated.


Data Structures - Segment Trees I was learning about segment trees and came across this:

  We have an array arr[0 . . . n-1]. We should be able to
  1 Find the sum of elements from index l to r where 0 <= l <= r <= n-1

  2 Change value of a specified element of the array to a new value x. We need to do arr[i] = x where 0 <= i <= n-1.

  A simple solution is to run a loop from l to r and calculate sum of elements in given range. To update a value, simply do arr[i] = x. The first operation takes O(n) time and second operation takes O(1) time.

  Another solution is to create another array and store sum from start to i at the ith index in this array. Sum of a given range can now be calculated in O(1) time, but update operation takes O(n) time now. This works well if the number of query operations are large and very few updates.

This is quoted from this web page.

The paragraph which I'm confused with is marked as bold. I think that the sum of a given range will only be calculated in O(1) time if l = 0, which is not always the case. Also, I can't seem to understand why did the update operation now takes O(n) time.

I hope it's just a small problem that can be easily explained. You can even explain the whole concept of segment trees here. I appreciate any help in any ways. Thanks.

Suppose you have created another array $S$ and stored sum from start to $i$ at $S[i]$. The sum of elements from index $l$ to $r$ inclusive is  $S[r]-S[l-1]$ for $l\ge1$, which takes two lookups and one subtraction, or $S[r]$ for $l=0$, which takes one lookup. So it takes $O(1)$ time.

Suppose you set $arr[k]$ to a new value, where $k=n/3$. Then you have to update $S[k], S[k+1], \cdots, S[n-1]$, which are roughly $n-n/3=2n/3$ numbers. That is, it takes $O(n)$ time. You can figure out all other cases of $k$.

"You can even explain the whole concept of segment trees here." That is exactly the purpose of that article and its follow-ups. Try reading them. Follow the recommendations thereof.


Growing a set given constraints I am trying to solve the following:

Given a set $S_0$, find min $|S|$ where $S_0 \subseteq S$ subject to:

$\forall s \in S$ $\exists$ $s_a, s_b \in S $ $|$ $ ( s_a \neq s, s_b\neq s ) \land ( s = s_a + s_b \lor s = 1 \lor s=2 ) $

Or in english, forall s in S there exists sa, sb in S such that sa != s, sb != s AND ( s = sa + sb OR s = 1 OR s = 2 )

For example if $S_0 = \{ 7, 9, 13, 22 \}$
then the solution is $S = \{ 1, 2, 3, 4, 7, 9, 13, 22 \}$ as

1 -> is 1 so allowed
2 -> is 2 so allowed
3 = 1 + 2
4 = 1 + 3
7 = 3 + 4
9 = 7 + 2
13 = 9 + 4
22 = 9 + 13
|S| = 8

$|S_0|$ is not particularly large but the numbers in $S_0$ can be very very large such that expressing all numbers possible is infeasible.

I have tried an ILP and ran out of memory expressing the binary variables for each number in the set.

My current approach ( which gives a pretty bad solution ) is pick the lowest number that is violated, heuristically pick two numbers and put them in the set. Repeat until all numbers meet constraints.

An approximate solution is fine. Anyone have any ideas?

I suggest you formulate this as an instance of integer linear programming (ILP).  Let $m$ be the largest number in $S_0$.  For each $i$ such that $1 \le i \le m$, introduce the zero-or-one variable $x_i$, with the intended meaning that $x_i=1$ means that $i \in S$ and $x_i=0$ means that $i \notin S$.

Now your constraints can be readily converted into linear inequalities: e.g., for each $s$ such that $2<s \le m$, we obtain that $x_s=1$ implies $\lor_{s_a,s_b} (x_{s_a}=1 \land x_{s_b}=1)$, where the disjunction is taken over all $s_a,s_b$ such that $1 \le s_a < s$ and $1 \le s_b < s$.  This can be converted into a linear inequality; see Express boolean logic operations in zero-one integer linear programming (ILP).  Also, for each $i \in S_0$, we add the requirement $x_i=1$.  Finally, we minimize $\sum_i x_i$.  Feeding this to an off-the-shelf ILP solver should yield a solution.

This should find the exact optimal solution, as long as the largest number in $S_0$ is not too large.  However, the running time is potentially exponential in $m$, the largest number in $S_0$.  I don't know if there is a polynomial-time solution.

(You could also formulate it as an instance of SAT instead of ILP.  This will require applying the Tseitin transform to convert the implication/disjunction into CNF, and it will require constructing an adder-circuit to add the requirement that the size of $S$ is at most $k$ and then doing binary search over $k$.  Then, you could feed it to an off-the-shelf SAT solver.  I have no idea whether this will work better than the ILP approach.)


Given a prime power, is it possible to efficiently compute the prime Suppose that I am given as input the number $p^i$ for some prime $p$ and some positive integer $i$. I wish to find $p$ and $i$.

Is there an algorithm to do this that works in time polynomial in the number of digits of $p^i$?

Yes, here is a simple approach (there are likely more efficient ones).

Let $n$ be the number given. Observe that $2 \leq p \leq n$ and $1 \leq i \leq \log_2(n)$. For each possible value of $i$ in the range $\{1, \ldots, \log_2(n)\}$, you can do a binary search for a $p$ in the range $\{2, \ldots, n\}$ such that $p^{i} = n$.


Do there exist fast multiplication algorithms for two integers with one of them being static? Let N and M be arbitrary 1024+ bit integers.
The objective is to compute the product of N and M (2048+ bits)
There exist various multiplication algorithms for various bit lengths (ex library: GMP). But there is always the assumption that both numbers are equally arbitrary.
Are there algorithms that are even faster under the assumption that for every time N changes, M changes K times with K being 2^20 or more?
An algorithm that given an integer, constructs/primes a special fast algorithm to compute a product just for that integer.
The only algorithm of this kind that I was able to find and that gave rise to this question is described in this paper: https://sci-hub.tw/10.1007/s00224-020-09986-5
C code provided by the author (GMP lib): http://www.fit.vutbr.cz/~ibarina/tmp/n.c
Summary: Uses the Collatz conjecture to do multiplication, O(Nk) where k is the number of odd integers in the Collatz sequence of a given odd operand. If k < log N it can beat current state of the art multiplication algorithms.

If $N$ is fixed (at least for a very long time), why not do some pre-computation. For example, you can pre-compute the product of $N$ with any 16-bit integer. Just save these values in a lookup table (there are only $2^{16} = 65536$ elements).
Represent $M$ in base $2^{16}$. i.e. $M = a_0 + a_1 * 2^{16} + a_2 * 2^{32} \ldots a_{63}(2^{16})^{63}$.
Well, $M = (N * a_0) + (N * a_1) * 2^{16} + (N * a_2) * 2^{32} \ldots ( N * a_{63}) * (2^{16})^{63}$. Instead of computing $N * a_i$, we can search the lookup table.


Can reversing the final and non-final states of a DFA produce the complement of the original language? Is this true? If I change all final states of a given Deterministic Finite Automata to non final states and all non final states to final states then does this new automata represent the complement of the language that was accepted by the original automata?

What if we talk about a Non deterministic finite automata instead of a DFA?

In DFAs, the path taken in the automaton are deterministic and reach one specific state, so all the strings in the language reach one accepted state and all the other strings on this alphabet reach non-accepting states. Switching the accepting and non-accepting path is equivalent to saying "accept every string that doesn't reach an accepting state in the original automaton, don't accept any string that reach an accepting state in the original automaton", in short, "Not in the language L of the original automaton", which is the complement of L.

In NFAs, it is quite easy to find contradiction to show that this statement is incorrect.

Consider the following 2-state NFA with the alphabet {a, b}:

state 1 (starting state, accepting state):
  input a -> go to state 1
  input b -> go to state 2

state 2:
  input a -> go to state 1 and 2
  input b -> go to state 2

The string "aaba" is accepted by this automaton. If we switch the accepting states, this string is still accepted by the automaton, and thus the two languages can't be the complement of each other.


Transforming a bounded knapsack to 0/1 knapsack Could I transform a bounded-knapsack problem into a 0/1 knapsack problem using the following way-:

Example: Lets says I have 3 types of items

$n=3$

$p_j=\{10,15,11\}$

$w_j=\{1,3,5\}$

$b_j=\{6,4,2\}$

$c = 10$

Here $n$ denotes the number of types of items, $p_j$ denotes the profit gained by including 1 item of a that particular type, $b_j$ denotes how many items of a particular are available. And $c$ denotes the total capacity of the knapsack.

So for each item of a particular type I transform the item by including all the various ways of adding it, so for the first item, since there are 6 of them I include in my transformed array all 6 ways of taking them ie. $(1,1*p_j),(2,2*p_j)..$ and so on. Example, the expansion of the first item would be:

$(1,10),(2,20),(3,30)...(6,60)$

So now the expanded array would contain $6+4+2=12$ elements.

Now if I use that against the standard dynamic programming approach for 0/1 knapsack problem would I be able to get the optimal solution ?

This text(page 3) introduces an algorithm that converts a bounded knapsack to 0/1 knapsack by adding $\sum_{j=1}^n \lceil log_2(b_j + 1) \rceil$ terms for each item. I am just wondering why that even works ?

An extract from the text reads the following:

  Notice that the transformations introduces $2^q$ binary combinations.

Can someone tell me how that works ? And if the above described way actually can lead to the optimal solution.

The approach you described does not work necessarily.

If you have the following situation (I made it simpler)

          | Profit | Weight | Total |
Object 1  |   5    |   3    |   3   |
Object 2  |   2    |   6    |   2   |

If you transform the problem according to your proposal we get the following situation

            | Profit | Weight |
Object 1.1  |    5   |   3    |
Object 1.2  |   10   |   6    |
Object 1.3  |   15   |   9    |
Object 2.1  |    2   |   6    |
Object 2.2  |    4   |  12    |

If the capacity of the knapsack here is $15$ the 0-1 knapsack algorithm will give you an invalid optimal answer. Taking object 1.2 and object 1.3 with profit $25$ and weight $15$, but this items are supposed to be exclusive (if you take 2 items of element 1 you can't take 3 also).

So another approach to transform it in a 0-1 knapsack is by creating a new item per instance.

            | Profit | Weight |
Object 1.1  |    5   |   3    |
Object 1.2  |    5   |   3    |
Object 1.3  |    5   |   3    |
Object 2.1  |    2   |   6    |
Object 2.2  |    2   |   6    |

The solution of this problem is equivalent to the original problem, but this don't scale very well, because if you have up to $10^9$ (or more) instance of an object, you need to create one item per instance.

Why this model works? and how can we improve it?
This model works because we split each object in several group of items (each group of size 1)and it allows us to combine them in order to get any number of objects up to the maximum. For example, if one object appear 7 times we split it in $(1,1,1,1,1,1,1)$ and if we want in the optimal solution only $3$ of them, then we pick any subset of size $3$ of this set.

But we can split them in other ways, keeping the condition that we can take a subset that sums whatever sum we want up to the maximum. For example you can split $10$ like $(1, 2, 3, 4)$, and this partition is useful since you can get any sum up to $10$. There is a canonical way to split a number in $log_2(n)$ numbers that has this property. Split the number in power of 2 starting from $1, 2, ...$ until you can't split it anymore, and add the remainder to the partition too.

For example:

5 -> (1, 2, 2)
10 -> (1, 2, 4, 3)
15 -> (1, 2, 4, 8)
1000 -> (1, 2, 4, 8, 16, 32, 64, 128, 256, 489)

Then if your original problem looks like this

          | Profit | Weight | Total |
Object 1  |   5    |   3    |   7   |
Object 2  |   2    |   6    |   17  |

We split $7=1+2+4$ and $17=1+2+4+8+2$
You transform it into this equivalent 0-1 knapsack problem

            | Profit | Weight |
Object 1.1  |   5    |   3    |
Object 1.2  |  10    |   6    |
Object 1.3  |  20    |  12    |
Object 2.1  |   2    |   6    |
Object 2.2  |   4    |  12    |
Object 2.3  |   8    |  24    |
Object 2.4  |  16    |  48    |
Object 2.5  |   4    |  12    |

The optimal answer here gives you a straight forward way to recover the original answer, and the amount of new elements you create for each different item is at most $O(log(frequency))$, where $freq$ is the instance you have of some particular object.


If a CNF contains only Horn and Xor clauses, then what is the complexity of determining Satisfiability? If a CNF contains only Horn and Xor clauses, and does not contain clauses of other types, then can its Satisfiability be determined in polynomial time?

Hint: Using XOR clauses you can express "$x = \lnot y$", and this allows you to simulate general clauses by Horn clauses.


Could following be a counter example to Church-Rosser (Confluence) theorem? According to the "Type Theory and Formal Proof" book, Church-Rosser theorem (confluence) is as follow:

  Suppose that for a given term $M$, we have $M \twoheadrightarrow_\beta N_1$ and $M\twoheadrightarrow_\beta N_2$. Then there is a $\lambda-term$ $N_3$ such that $N_1\twoheadrightarrow_\beta N_3$ and $N_2\twoheadrightarrow_\beta N_3$.

But if we take $(\lambda u.v)((\lambda x.xx)(\lambda x.xx))$ expression as $M$, then it will reduce to $v$ if we start with the left sub term and reduces to $(\lambda u.v)((\lambda x.xx)(\lambda x.xx))$ if we start with the right sub term. And they would never reduce to equal terms if we keep reducing the sound one using the right sub term since it would keep converting to itself for ever.Isn't the above example a refutation of the CR theorem, or I have missed a point somewhere?!

If we keep reducing the right subterm, then yes, we will never get to $v$. But noone says that we are restricted to this decision. The Church-Rosser theorem does not claim that any possible reduction series must lead to $N_3$. Church-Rosser just states that $N_2 \twoheadrightarrow_\beta N_3$, i.e. that there exists some beta reduction series that will lead from $N_2$ to $N_3$. And it is obvious that no matter how many times we just reduce back to $(\lambda u.v)((\lambda x.xx)(\lambda x.xx))$, at any point we can choose our next reduction step to be on the left-hand side, which will immediately get us to $v$. So it is possible to find a reduction series from both $N_1: v$ and $N_2: (\lambda u.v)((\lambda x.xx)(\lambda x.xx))$ to $N_3:v$ -- and that's all the Church-Rosser theorem states.


What is the difference between quantum TM and nondetermistic TM? I was going through the discussion on the question How to define quantum Turing machines? and I feel that quantum TM and nondetermistic TM are one and the same. The answers to the other question do not touch on that. Are these two models one and the same?

If no,

What are the differences between quantum TM and NDTM?
Is there any computation which a NDTM would do quicker than Quantum TM?
If this is the case then quantum TM is a DTM, then why is there so much fuzz about this technology, we already have so many DTM. Why to design a new DTM in the end?

As a general preamble, QTMs, TMs and NTMs are all different things (taking huge liberties with a bunch of unspoken assumptions).

I'll assume you know what a Turing Machine is.

 A NTM is a TM where, at any state, with any symbol, the transition function is allowed to have a number of choices of action that is not precisely $1$, i.e. $0$ or more than $1$ (a deterministic TM must have exactly one action for each symbol at each state, though the $0$ case is easy to deal with). When faced with a situation where there are several choices of transition a NTM will make the choice that will ultimately take it to an accepting state, if such an option exists.

In contrast a QTM is a model of quantum computation, as detailed in the thread you linked. It is not nondeterministic, not all. Probably the key high level differences between a QTM and a TM is that a QTM has as its state a linear combination of the basis states (again, it's all in that other thread) and that it's probabilistic, that is, the accuracy of its ouput is bounded by some probability less than $1$ (broadly speaking).
Just to be really really clear on a point that catches many people, nondeterminism is not randomness, it's not parallelism, it's a theoretical construct that has nothing to do with either of those.

 The full answer to this depends on some complexity theoretic assumptions. Taking a particular standpoint (that $QMA \supset BQP$ and $NP \supset P$), the answer is yes. $NP$-complete problems can be solved by a NTM in polynomial time, and it also seems that $NP\text{-complete} \cap BQP = \emptyset$, so they can't be solved by a QTM in polynomial time.
Again, this is all dependent on which way the cards fall with a variety of complexity classes. If it turns out that $QMA = BQP$ then the answer is no, for example.

 The first thing to say here is to be careful about confusing TMs (of any kind) and computers. A TM is not a computer, a QTM is not a quantum computer. TMs (of any kind) model computation. What a given computer can do is governed by this, but this is quite different to saying that the thing I'm typing this on is a TM.
Having said that, if we speak loosely and lazily identify QTMs with quantum computers and TMs with standard computers, then (again under certain complexity assumptions) it seems that quantum computers can quickly do certain tasks that seem hard for standard computers (factoring, discrete logs, a really particular type of searching, and a couple of others). However these problems aren't known to be hard in the $NP$-complete sense either, it seems quantum computers offer capabilities that extend a standard computer, but in a different direction to what would be needed to solve $NP$-complete problems quickly.

Again just to be really clear, I've glossed over a lot of computational complexity here, if you really want to understand how everything fits together, you'll need start digging in to the literature.


What could 'two characters are terminals' mean? In the context of this statement, what does 'a & b are terminals' mean?

  Stacks and queues can be used for determining whether a particular
  input string is in the language or not.

  L = {a^nb^m | m,n >= 0, m >= n, and a & b are terminals}

  Sample strings in L : abb, aabb, aabbb

  Sample strings NOT in L : aab, ba

It means that $a$ and $b$ cannot be further decomposed. For example we might consider the language
$$
L_1=\{r^ns^m\mid n, m \ge 0, m\ge n, r\text{ and }s \text{ are 2-character strings over } \{a, b\}\}
$$
In this language, $r$ and $s$ could be any of $aa, ab, ba, bb$, so a string in $L_1$ could be $bababbbbbb$, since with $r=ba, s=bb$ we could write it as $(ba)^2(bb)^3$. In effect, saying "$a$ is terminal" asserts that it's a character in the underlying alphabet.

The original definition of $L$ is reasonable, but rarely used in my experience. An equivalent statement would be
$$
L=\{w\in \{a, b\}^*\mid w=a^nb^m, n, m\ge 0, m\ge n\}
$$
or the alphabet $\{a, b\}$ would be inferred from context and usually wouldn't be stated. On any of my students' work, I'd accept
$$
L=\{a^nb^m\mid n, m\ge 0,m\ge n\}
$$


What is the difference between a scripting language and a normal programming language? What is the difference between programming language and a scripting language?
For example, consider C versus Perl.

Is the only difference that scripting languages require only the interpreter and don't require compile and linking?

I think the difference has a lot more to do with the intended use of the language.

For example, Python is interpreted, and doesn't require compiling and linking, as is Prolog. I would classify both of these as programming languges.

Programming langauges are meant for writing software. They are designed to manage large projects. They can probably call programs, read files, etc., but might not be quite as good at that as a scripting language.

Scripting langauges aren't meant for large-scale software development. Their syntax, features, library, etc. are focused more around accomplishing small tasks quickly. This means they are sometimes more "hackish" than programming langauges, and might not have all of the same nice features. They're designed to make commonly performed tasks, like iterating through a bunch of files or performing sysadmin tasks, to be automated.

For example, Bash doesn't do arithmetic nicely, which would probably make writing large-scale software in it a nightmare.

As a kind of benchmark: I would never write a music player in perl, even though I probably could. Likewise, I would never try to use C++ to rename all the files in a given folder.

This line is becoming blurrier and blurrier. JavaScript, by definition a "scripting" langauge, is increasingly used to develop "web apps" which are more in the realm of software. Likewise, Python initially fit many of the traits of a scripting language but is seeing more and more sofware developed using Python as the primary platform.


Definition of prefixes of a string From Wikipedia:

  The prefixes of a string is the set of all prefixes to a string, with respect to a given language:
  $$
    \operatorname{Pref}_L(s) = \{t \mid s=tu \mbox { for } t,u\in \operatorname{Alph}(L)^*\}
$$
  here $s\in L$.

So is it equivalent to
$$
    \operatorname{Pref}_L(s) = \{t \mid t \mbox { is the first $n$ part of $s$}, \forall n \in \{1, \dots, \mbox { length}(s)\} \}?
$$

No.  As you have defined it, $t$ is only in the language if it is every prefix, except $\varepsilon$, of $s$.  That definition describes $\emptyset$ if $|s|$ is not 1, or $\{s\}$ if $s$ is a single symbol.  If you change ∀n∈{1,…, length(s)},  to $\text{s.t.}$ $1 \leq n \leq |s|$, then it would be almost equivalent.  However the first language includes the empty string.

Also "first n part of" is not a very good way to describe a prefix of length n.  It could be ambiguous.  And you should define what $t$ is, i.e. $t \in \Sigma^*$.


Time complexity of Depth First Search Please forgive me for asking a novice question, but I'm a beginner at algorithms and complexities, and it's sometimes hard to understand how the complexity for a specific algorithm has come about.

I was reading the DFS algorithm from Introduction to Algorithms by Cormen, and this was the algorithm:

G        -> graph
G.V      -> set of vertices in G
u.π      -> parent vertex of vertex u
G.Adj[u] -> adjacency list of vertex u

DFS(G)
1   for each vertex u ∈ G.V
2       u.color = WHITE
3       u.π = NIL
4   time = 0
5   for each vertex u ∈ G.V
6       if u.color == WHITE
7         DFS-VISIT(G,u)

DFS-VISIT(G,u)
1   time = time + 1            // white vertex u has just been discovered
2   u.d = time
3   u.color = GRAY
4   for each v ∈ G.Adj[u]      // explore edge u
5       if v.color == WHITE
6           v.π = u
7           DFS-VISIT(G,v)
8   u.color = BLACK            // blacken u; it is finished
9   time = time + 1
10  u.f = time

It then said lines 1-3 and 5-7 are O(V), exclusive of the time to execute the calls to DFS-VISIT().
In DFS-VISIT(), lines 4-7 are O(E), because the sum of the adjacency lists of all the vertices is the number of edges. And then it concluded that the total complexity of DFS() is O(V + E).

I don't understand how that came about. DFS-VISIT() is called inside DFS(). So, if lines 5-7 of DFS() are O(V) and DFS-VISIT() is O(E), then shouldn't the total time complexity of DFS() be O(VE)?

The book is counting the number of times each line is executed throughout the entire execution of a call of DFS, rather than the number of times it is executed in each call of the subroutine DFS-VISIT. Perhaps the following simpler example will make this clear:

PROCEDURE A(n)
1  global = 0
2  for i from 1 to n:
3      B(i)
4  return global

PROCEDURE B(i)
1  global = global + 1

In each execution of A, line 1 of B is executed $n$ times, and B itself is executed $n$ times. Nevertheless, the running time is $O(n)$ rather than $O(n^2)$.

Here is another example, in which an array $T[1\ldots n]$ is involved.

PROCEDURE COUNT(n, T[1...n]):
1  count = 0
2  index = 1
3  while index <= n:
4    ADVANCE()
5    count = count + 1
6    index = index + 1
7  return count - 1

PROCEDURE ADVANCE():
1  while index <= n and T[index] == 0:
2    index = index + 1

The procedure COUNT counts the number of 1s in the input array T. Even though ADVANCE could be called up to $n$ times by COUNT and the worst-case running time of ADVANCE is $O(n)$, lines 1–2 of ADVANCE run at most $n$ times, and so the overall running time is $O(n)$ rather than $O(n^2)$.


Term Rewriting vs Unification How is term rewriting different from unification, and what's the difference between term rewriting languages and logic programming, like Prolog?

Term rewriting is a rewriting formalism. Starting with a term we rewrite the term according to the term rewriting rules until a normal form is found. Unification is finding a solution (substitution with specific properties) to a problem (a pair of terms).

Term rewriting uses a notion called "pattern matching". What you probably meant is: what is the difference between matching and unification?

Let two terms $t_1$ and $t_2$ be given.

If we want to unify $t_1$ and $t_2$, we search for a substitution $\sigma$ such that $t_1\sigma = t_2\sigma$. On the other hand, if we want to match $t_1$ into $t_2$, we are looking for a substitution such that $t_1\sigma = t_2$. That is, we apply the substitution only on $t_1$.

Logic programming is a programming paradigm which is based on resolution, which is a proof method for logics. In logic programming unification plays an important role.


Finding lowest "pass" between two points on a map? (I expect that the hard part of this question is getting the right language for the problem.  My attempts at searching for an answer didn't get anything useful, which suggests to me that whatever they are, I'm not using them!)

Consider a map where each x,y coordinate has an associated "height" value.  If we have two points (each of which is at a local minimum height) on this map, we can consider the set of all possible paths between those two points.  Each path has a maximum height along the path; call this the "pass height" of the path.  I'm interested in the minimum value of the pass height over the set of possible paths.

I'm calling this a "lowest pass", because in real maps, these paths with minimum height are the passes through the mountains.

What is an algorithm that will allow me to determine this minimum pass height?  I'd be happy either with an algorithm that assumes a discrete grid of finitely-spaced points, or an algorithm that approximates the solution on a continuous surface with numerical iteration of some sort.

I'd also particularly like a solution that will work in a high-dimensional space, but one in 2-space would be a good start.

A simple solution to this would be to implement it as any normal pathfinding algorithm (say, A*), but then render in your map any height over a threshold as impassable, and any height under the threshold as passable, and then continuously run the pathfinding algorithm for threshold heights between the minimum cell height and the maximum cell height. The first time you can path from start to end is the lowest possible height.

This has some performance implications for maps with a large difference between highest and lowest points, but you use a search algorithm other than a linear search to find the upper and lower bounds and close in on the boundary.

Many pathfinding algorithms are already generalised to n-dimensions, so to generalise this is simply the case of picking the correct dimension to use as the varying threshold. Essentially, for a map of n dimensions (say, a 2D map + height), you path find in that many dimensions with the height being made into a passable/impassable cost.


If $T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$, what is $T(m^2)$? $T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$
  $T(1)=1$
  The value of $T(m^2)$ for m ≥ 1 is?

Clearly you cannot apply master theorem because it is not of the form $T(n)=aT(\frac{n}{b})+f(n)$
So I tried Back Substitution:
$T(n)=T(n-1)+\lfloor\sqrt{n}\rfloor$
$T(n-1)=T(n-2)+\lfloor\sqrt{n-1}\rfloor$
therefore,
$T(n)=T(n-2)+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
$T(n)=T(n-3)+\lfloor\sqrt{n-2}\rfloor+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
.
.
$T(n)=T(n-(n-1))+...T(n-k)+\lfloor\sqrt{n-(k-1)}\rfloor+...+\lfloor\sqrt{n-2}\rfloor+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
.
.
$T(n)=T(1)+...T(n-k)+\lfloor\sqrt{n-(k-1)}\rfloor+...+\lfloor\sqrt{n-2}\rfloor+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
$T(n)=T(1)+...+\lfloor\sqrt{n-2}\rfloor+\lfloor\sqrt{n-1}\rfloor+\lfloor\sqrt{n}\rfloor$
I'm stuck up here and the answer is given as -

  $T(m^2)=\frac{m}{6}(4m^2 - 3m + 5)$

how to solve and reach the answer?

For a slightly different way to look at his problem, consider your original equation,
$$
T(n) = T(1)+\lfloor\sqrt2\rfloor+\lfloor\sqrt3\rfloor+\dotsb+\lfloor\sqrt n\rfloor
$$
Now the key here is to group the terms with the same values of $\lfloor\sqrt k\rfloor$:
$$\begin{align}
T(n) &= (T(1)+\lfloor\sqrt2\rfloor+\lfloor\sqrt3\rfloor)\\
 &+(\lfloor\sqrt4\rfloor+\lfloor\sqrt5\rfloor+\lfloor\sqrt6\rfloor+\lfloor\sqrt7\rfloor+\lfloor\sqrt8\rfloor)\\
 &+(\lfloor\sqrt9\rfloor+\lfloor\sqrt{10}\rfloor+\lfloor\sqrt{11}\rfloor+\lfloor\sqrt{12}\rfloor+\lfloor\sqrt{13}\rfloor+\lfloor\sqrt{14}\rfloor+\lfloor\sqrt{15}\rfloor)\\
 &+\dotsc
\end{align}$$
and observe that each summand will have $2k+1$ terms, since the difference $(k+1)^2-k^2 = 2k+1$:
$$
T(n) = (1\cdot3)+(2\cdot5)+(3\cdot 7)+(4\cdot 9)+\dotsb
$$
so we'll have, with $n=m^2$
$$\begin{align}
T(m^2) &= (1\cdot3)+(2\cdot5)+\dotsb+\left(\left\lfloor\sqrt{(m-1)^2}\right\rfloor+\dotsb+\left\lfloor\sqrt{m^2-1}\right\rfloor\right)+\left\lfloor\sqrt{m^2}\right\rfloor\\
 &=\sum_{k=1}^{m-1}k(2k+1)+m =\sum_{k=1}^{m-1}(2k^2+k)+m\\
 &=2\sum_{k=1}^{m-1}k^2+\sum_{k=1}^{m-1}k+m\\
 &=2\frac{(m-1)(m)(2(m-1)+1)}{6}+\frac{(m-1)(m)}{2}+m\\
 &=\frac{m}{6}(4m^2-3m+5)
\end{align}$$
as required.


How to perform local search to find maximal induced subgraphs? I'm looking for efficient ways to perform local search to find maximal induced subgraphs that satisfy certain properties : a tree, a forest or a bipartite subgraph for example.

What I mean by local search is moving from solution to solution by applying local changes, until a solution deemed optimal is found or a time bound is elapsed.

All three problems are easy to formalize as local search problems.  Let $f$ be a function that measures the quality of a solution $s$, in your cases

$f(s)$ is

the number of edges (or vertices) in the tree $s$
the number of edges (or vertices) in the forest $s$
the number of vertices (?) in the bipartite graph $s$

and your goal is to maximize $f$.

Lastly, you need to define a neighborhood function $N(s)$ that gives all possible ways of modifying a current solution $s$ to a new solution $s'$.

To illustrate $N(s)$ in the simplest case, the tree:
$$ N(s) = \{ X \subseteq V(G) \mid \text{is_tree}(V(s) \setminus X \cup (X \setminus V(s)) \}, $$

and my apologies for the terse syntax.  It is simply all the ways you can delete a certain set of vertices from the solution $s$, simultaneously adding a different set of vertices, at the same time keeping the property that the new $s'$ is a tree.

Now, the search algorithm simply starts with a random solution (tree) $s$ (which might be the empty tree), and just randomly walk $N(\cdot)$.