Hierarchial clustering cannonnical representation? I have to handle large binary dataset. That is one of the reasons I have to build my own Hierarchical Clustering. As I digged into the algorithms I was surprised and not ;) to find that it is possible to have multiple (not just two) vectors that have the same distance (hamming,overlap,...), so you can pair them differently in a 'correct' way.
F.e. using overlap as similarity mesaure ... the following 3 vectors have overlap of 2 and there are 2 different correct pairing.
 sequence : 110,101,111

what this means is that there is multiple ways to cluster those :
 ((110,111),101)  vs (110,(111,101))

 sequence : 110,101,111,011

 (110,((111,011),101))  vs ((110,(111,011)),101)

Let me illustrate it with integers  :
 2,6,8,4
 (2,((4,6),8))  vs ((2,(4,6)),8) vs ....

What this means is that there are no canonical way of clustering/dendogram .
How do you handle that ?
Is there a different type of clustering that can have canonical/single representation ?

You can always adjust your algorithm to use a deterministic tie-breaking rule, e.g., sort the data points before applying the clustering algorithm, and always break ties in favor of the earliest/leftmost item.  This yields a deterministic algorithm, so if you give it exactly the same input both times, it will produce the same clustering both times.  I can't tell whether this is what you are looking for or not.


Natural candidates for the hierarchy inside NPI Let's assume that $\mathsf{P} \neq \mathsf{NP}$. $\mathsf{NPI}$ is the class of problems in $\mathsf{NP}$ which are neither in $\mathsf{P}$ nor in $\mathsf{NP}$-hard. You can find a list of problems conjectured to be $\mathsf{NPI}$ here.

Ladner's theorem tells us that if $\mathsf{NP}\neq\mathsf{P}$ then there is an infinite hierarchy of $\mathsf{NPI}$ problems, i.e. there are $\mathsf{NPI}$ problems which are harder than other $\mathsf{NPI}$ problems.

  I am looking for candidates of such problems, i.e. I am interested in pairs of problems
  - $A,B \in \mathsf{NP}$,
  - $A$ and $B$ are conjectured to be $\mathsf{NPI}$,
  - $A$ is known to reduce to $B$,
  - but there are no known reductions from $B$ to $A$.

Even better if there are arguments for supporting these, e.g. there are results that $B$ does not reduce to $A$ assuming some conjectures in complexity theory or cryptography.

Are there any natural examples of such problems?

Example: Graph Isomorphism problem and Integer Factorization problem are conjectured to be in $\mathsf{NPI}$ and there are argument supporting these conjectures. Are there any decision problems harder than these two but not known to be $\mathsf{NP}$-hard?

I've found a nice problem called ModularFactorial. Take as input two $n$-digit integers $x$ and $y$, and output $x! \mod y$. This problem is at least as hard as Factoring and not know to be hard for FNP. The reference is the recent (and beautiful) book by Cristopher Moore and Stephan Mertens The Nature of Computation, page 79.


Find the Context Free Grammar Let $\Sigma = \{a, b\}$. For each of the following languages, find a grammar that generates it.

(a) $L_1 = \{a^n b^m : n\geq 0, m>n\}$

(b) $L_1^3$

(C) $L_1^*$

I know the grammar for the language $L_1$, that is

$S \rightarrow aSb \mid bA$
$A \rightarrow bA \mid \epsilon$

please help me to find the grammars for another two languages.

b) Introduce a new start symbol $S_1$ and a new production rule $S_1 \rightarrow SSS$

c) Introduce a new start symbol $S_2$ and a new production rule $S_2 \rightarrow S_2S \mid \epsilon$


Infinite Intersection/Union of regular languages Hello I'm having trouble understanding how an intersection/union of regular languages can be regular and in other case non-regular.

Can someone please give me some good examples?

For every word $w$, there's a language $\{ w\}$, which is regular, and $\Sigma^* \setminus \{ w\}$, which is also regular.

But, we can express every language (regular or not) $L$ as an infinite union: $L = \bigcup_{w \in L} \{ w \}$, which is an infinite union of regular languages.

For intersection, you do the opposite:

$L = \bigcap_{w \not \in L} (\Sigma^* \setminus \{w \})$.

So, we know that there are regular languages, and non-regular languages, and they can all be expressed as infinite unions or intersections of regular languages.


Which is the proper algorithm to figure repeated substrings of longest total length? Given a string $S$ and a substring $T$, define the value of $T$ to be the total length (in characters) of all non-overlapping instances of $T$ in $S$.  In other words, the value of $T$ is the length of $T$, times the number of times that $T$ occurs in $S$ without overlap.

I need an algorithm that does the following:

Given a string $S$, find the substring $T$ whose value is maximal, out of all substrings of length at least two; the index of each location where $T$ appears in $S$; and the value of $T$ (the total number of characters across all of those occurrences of $T$).

You can assume the string $S$ is ANSI encoded, where each character is one byte.

Example:

String => "AOOISDF000923RJJASPDFIJJ1023ASPD499FJJDSJIK"

Has the following repetitions:
1 - "DF", two times, total characters (4)
2 - "23", two times, total characters (4)
3 - "JJ", three times, total characters (6)
...
N - "ASPD", two times, total characters (8)

The desired output would be ASPD, because it has produced the largest total amount of characters (8).

Is there an efficient algorithm for this problem?  Is there a search term or name for this that I could use to search for it, or papers in the literature that describe techniques for this problem?

You might want to check out the literature on the longest repeated substring problem, which is closely related but is trying to optimize a different metric.  There are many algorithms and techniques; it's possible some of them could be adjusted to apply to your problem.

For instance, one can find the optimum solution to your problem in $O(nr)$ time using Rabin-Karp's method, where $r$ is the length of the longest repeated substring in $S$.  First, we compute $r$ using any standard method.  Then, for each $i$ in the range $1,2,\dots,r$, we look for the substring $T$ of length $i$ that is repeated the most number of times (without counting overlaps).  This can be done in $O(n)$ time for a fixed value of $i$, by using a rolling hash to compute the hash of all length-$i$ substrings of $S$ and for each such length-$i$ substring, compute the number of times it is repeated (without counting overlaps).  This can be done using a hashtable and a greedy algorithm (each time you see a substring $T$, if it doesn't overlap with the last accepted occurrence of $T$, increment the count for $T$ and accept this occurrence, otherwise reject it).

For many distributions on input strings, $r$ is relatively small compared to $n$: e.g., $r = O(\lg n)$.  If that applies to your situation, then this Rabin-Karp-based method will be easy to implement and perform reasonably well.

You could also look at suffix trees or suffix arrays.  Each internal node in the suffix tree represents a candidate for the substring (a substring that occurs more than once in $S$).  However, it's not quite clear to me at the moment how to efficiently account for overlap according to your problem statement, so I don't have a specific algorithm to suggest.


What is a malformed token? I am reading Programming Language Pragmatics by Michael Scott. He says that on a first pass, a compiler will break a program into a series of tokens. He says that it will check for malformed tokens, like 123abc or $@foo (in C).

What is a malformed token? A variable that does not meet the rules of variable-naming? An operator that does not exist (ex. "<-")?

Is this analogous to a misspelled word?

The basic syntactic units in any textual programming language are tokens, which are, if you wish, the words in the programming language. The compiler parses these tokens to build sentences and so forth.

A malformed token is a string of characters that is not a valid word for the programming language.

It is not a variable that doesn't match the naming rules – not all tokens are variables. It is not an operator that is unknown – sometimes operators can be defined by the programmer. It is one of the smallest pieces of syntax that will never correspond to something sensible.


$a^{2n}$ where $n\geq1$ is not Regular using Pumping Lemma I'm having trouble understanding Pumping Lemma for $RL$ , i know that $0^{2n}$ is regular and we can design a FSM for it.Here's my pumping Lemma statement

Let $p$ be the pumping length and my string is $0^{2p}$
1. $z=|0^{2p}|=> 2p > p $ (Satisfied)
2. $z=uvw$ such that $|uv|\geq p$, I'm choosing $|u|=n-p$ and $|v|=p$ so that $|uv|\geq p$ (Satisfied)
3.Now $u(v^i)w$, I choose $i=3$ then $|uvw|=2(n+p)$ which is even
But if $n=2$ then $|uvw|=2n+p$, how do i know if this could be even/odd?

You can't prove that a language is regular by applying the pumping lemma.

Regular Languages are a subset of Languages that satisfy the pumping lemma. So you can only proof irregularity with the lemma. (By assuming that the language is regular and coming to a contradiction)

One way to show that a language is regular, is e.g. constructing a Regular Expression, NFA or DFA (all of these being equivalent).


Getting the essential from the fundamental matrix Is it possible to get E from F? I suppose that can't work, because then I could calculate the the extrinsic (and maybe also intrinsic?) parameters of the cameras without a calibration object of known size etc. like so:

Pick (8) corresponding points in images i1 and i2
Calculate F with the eight-point-algorithm
Calculate E from F
Determine relative position and orientation of cameras from E (and maybe it is also possible to get the intrinsic parameters, K?)

You can only get the essential matrix from the fundamental matrix if you know the camera intrinsics:

E = K' * F * K

where K is the intrinsic matrix and K' is its transpose.


Choice of algorithm for hierarchical clustering for minimizing network communication costs Suppose I have a large distributed task running on a cluster system where part of the workload is compute bound and part depends on network performance.  Data transfer is not completely homogeneous between processes - some communication pairs are more or less sensitive to bandwidth and latency than others.

We've profiled this and have a square matrix describing how much
information is transferred between each pair of processes during the job.

We also know how the network is laid out and can approximate a scalar communication cost for each entry in that matrix.

Starting from that point, which clustering algorithms should I be looking at to permute that matrix to minimize total communication distance?  Or, I think equivalently: how can I compute a near-optimal clustering of processes so that the processes that communicate the most are closest to each other on the network?

This is a form of assignment problem; in particular, it is an instance of quadratic assignment problem.  There are some known techniques available for solving this sort of problem.

Using integer linear programming

One approach is to use integer linear programming.

Let $d_{p,q}$ denote the amount of data communicated between processes $p$ and $q$, for each pair of processes $p,q$.  Also, let $c_{i,j}$ denote the communication cost for data sent between machines $i$ and $j$, for each pair of machines $i,j$.  These are given.

The goal is to find an assignment of processes to machines, that minimizes the total communication cost.  I'll assume that you only allow one process to be assigned to each machine.  We can model this as follows.  For each process $p$ and each machine $i$, let $x_{p,i}$ be an unknown that is either 0 or 1, with the intent that $x_{p,i}=1$ means process $p$ is assigned to machine $i$.  You can force it to be 0 or 1 with the constraint $0 \le x_{p,i} \le 1$.  You can force each process to be assigned to one machine with the constraint

$$\sum_i x_{p,i} = 1.$$

You can also force each machine to be assigned at most one process with the constraint

$$\sum_p x_{p,i} \le 1.$$

The total communication cost is

$$\sum_{p,q,i,j} x_{p,i} x_{q,j} c_{i,j} d_{p,q},$$

where the sum is over all $p\ne q$ and $i \ne j$.  That's what we'd like to minimize.

This is not yet a linear objective function, so we can't apply integer linear programming directly, but we can transform it into an integer linear program as follows.  Let $y_{p,q,i,j} = 1$ if process $p$ is assigned to machine $i$ and process $q$ is assigned to machine $j$.  We have $y_{p,q,i,j} = x_{p,i} \land x_{q,j}$.  Now logical AND can be expressed in an integer linear program by adding the constraints

$$y_{p,q,i,j} \ge x_{p,i} + x_{q,j} - 1$$
$$y_{p,q,i,j} \le x_{p,i}$$
$$y_{p,q,i,j} \le x_{q,j}$$
$$0 \le y_{p,q,i,j} \le 1.$$

With these extensions, the total communication cost becomes

$$\sum_{p,q,i,j} y_{p,q,i,j} c_{i,j} d_{p,q},$$

which is a linear function.  Thus, you now obtain an integer linear program, where the goal is to minimize the total communication cost, subject to the constraints listed above.  You could try solving it using an off-the-shelf integer linear programming (ILP) solver.

There is no guarantee that this will efficiently find an optimal solution -- after all, integer linear programming is NP-hard in the worst case -- but in practice ILP solvers often work surprisingly well on many problems.  So, you could give it a try and see how well it works on  your particular problem instances.  I don't know if there is a better algorithm, but this is one approach you could try.

P.S. In fact, in this particular case, you could skip the constraints $y_{p,q,i,j} \le x_{p,i}$ and $y_{p,q,i,j} \le x_{q,j}$ without changing the final solution.  This makes the program a little bit simpler, at the cost of making it a little harder to understand why it "works" correctly for your problem.

Dedicated algorithms

An alternative is to use a dedicated algorithm for the quadratic assignment problem.  For instance, Wikipedia mentions QAPLIB, a dedicated solver for instances of the quadratic assignment problem.  You could try using QAPLIB on your problem instance, to see how well it works.

There may be other algorithms for the quadratic assignment problem -- I recommend doing a literature search to see what you can turn up.


Calculating the average waiting time of tasks I have proposed a load balancing algorithm for a group of homogeneous processing devices and now I want to measure the average waiting time to see if my algorithm is successful in decreasing the waiting time. I have considered number of tasks on each device as the load of that device.

Imagine at first there are 54 tasks that is distributed like this between devices:

  device1 = 32

  device2 = 20

  device3 = 2

And after load balancing 15 tasks are transferred from device1 to device3 and these values change to:

  device1 = 17

  device2 = 20

  device3 = 17

Now I want to calculate and compare average waiting time before and after the load balancing, but I'm confused about which tasks to consider.

Should I consider all 54 tasks and measure the waiting time of all these 54 tasks

Or

should I only consider 15 tasks that were transferred and calculate the waiting time of these 15 tasks before and after load balancing?

From the two options, the first is the (only) reasonable approach. The second one is absolutely useless; details follow:

If you are trying to minimize the waiting time of the tasks that were shifted, then the best algorithm simply reschedules no tasks at all. The total time of transferred tasks is zero and, thus, optimal. Even if you require at least one task to be transferred, the best algorithm then simply picks the one with the least running time and transfers it to the least loaded queue. In both cases it could hardly be said the algorithm does something useful.
If you are trying to maximize the waiting time of the tasks which were rescheduled, then consider the algorithm which permutates all tasks between the devices. This naturally maximizes said measure and, again, hardly qualifies as a sensible load balancing algorithm.


Easy reduction from 3SAT to Hamiltonian path problem There is a reduction in Sipser's book "Introduction to the theory of computation" on page 286 from 3SAT to Hamiltonian path problem.

  Is there a simpler reduction?

By simpler I mean a reduction that would be easier to understand (for students).

  Is there a reduction that uses linear number of variables?

The reduction in Sipser uses $O(kn)$ variables where $k$ is the number of clauses and $n$ is the number of variables. In other words, it is possible for the reduction to blow the size from $s$ to $O(s^2)$. Is there a simple reduction where the size of the output of the reduction is linear in the size of its input?

If it is not possible, is there a reason? Would that imply an unknown result in complexity/algorithms?

The number of vertices in the well-known reduction from 3SAT to directed Hamiltonian Path(dHAMPATH) can be easily reduced to $O(n+k)$, where $n$ is the number of variables and $k$ is the number of clauses, therefore the size of the constructed graph instance is linear to the size of the original 3SAT instance.

In the original reduction, we have start vertex and end vertex, $k$ vertices for clauses, $n$ lists of length $4k$ for variables. The idea is that we don't have to construct list of length $4k$ for each variable, we can construct list according to the number that the variable appears in all the clauses. Since the total number of appearances of variables in clauses is $3k$, it is $O(n+k)$.


Algorithms for "mostly-SAT?" This is third-hand, so please bear with me.  A collaborator was at a review meeting where he heard another participant make the claim that given an assignment for a SAT problem that satisfies (some high percentage) of clauses, there are polynomial time algorithms that finish the problem.

Is this true?  Can someone point me to some references?

This cannot be true, since you could use such an algorithm to solve SAT itself in polynomial time. Given a SAT instance $\varphi$, construct a much larger instance $\psi$ which contains $\varphi$ as well as many copies of the clause $x$, where $x$ is a new variable not appearing in $\varphi$. It is easy to find an assignment satisfying almost all clauses of $\psi$. Now run your algorithm. If it succeeds, then $\varphi$ is satisfiable; and moreover, if $\varphi$ is satisfiable then it should, indeed, succeed. Thus $\varphi$ is satisfiable iff your algorithm finds a satisfying assignment within the promised running time.

Perhaps the participant meant an assignment which is close to a satisfying assignment, as in Schöning's kSAT algorithm; see for example Eppstein's lecture notes.


Lower bound for comparison algorithm - checking whether permutation is odd or even I consider problem:  proving lower bound for comparison algorithm that check whether permutation is odd or even.
I know that this bound is $\Omega(n\lg n)$.

Could you give me a clue ?

Hint: Show that if you know the parity of the input permutation then you know the entire permutation, and so you can sort the list.

In more detail, the information that you have at any leaf of the decision tree can be represented as a partial order on the elements. Show that if this partial order is not linear then it has a linear completion which is an odd permutation and another linear completion which is an even permutation.


P Vs NP can never be proven one way or the other! Okay, so I was reading a bit about P vs NP problems. And I found out that proving P Vs NP is an NP problem.

And since if we prove that any problem in NP is a P that would mean that we have NP=P.

So by that logic either NP==P or it can never be proven that NP is not P and if somebody proves that, then won't they be contradicting the result itself. I mean they solved one NP problem which was this proof so by that logic all other problems should now be in class P.

Let me know if I got something wrong here.

And I found out that proving P Vs NP is an NP problem.

I think the two different meanings of the word "problem" are mixed here.
When we discuss P and NP, they are the class of decision problems, which are essentially maps from the set of bits sequence to boolean values.
On the other hand, "NP =/= P" is a long standing mathematical problem (general meaning,) but "NP =/= P" itself is a single proposition, and usually it's not considered as decision problem.

If you convert "NP =/= P" to a decision problem as the map from single point to true/false (this is completely valid formalization), its complexity is constant time (algorithm can simply return true or false, though we don't know which one is correct,) so it's in P and NP.

  if somebody proves that, then won't they be contradicting the result itself

Proving "NP =/= P" means we know the correct return value in the algorithm above, and that doesn't contradict with anything. The result simply claims there is a NP problem that is not P. The decision problem "NP =/= P" is just an instance within class P. Both facts can hold simultaneously.


How to prove that if the set and its complement are recursively enumerable, then both are recursive? How to prove that if the set and its complement are recursively enumerable, then this set and its complement are recursive?
My idea is that we can make the characteristic function of recursively enumerable set to be a total function using characteristic function of the complement (we can compute both $\chi_A$ and $\chi_\overline{A}$ step by step, alternating steps between them, and when either one stops, we can determine if the element belongs to the set $A$ or its complement).
Is it right?

Roughly, yes, that's the right idea.

I think there are a few small issues though.

First, you can not compute the characteristic function $\chi_A$, since this is computable only when the set is recursive. What you can compute is the semi-characteristic function, whose domain is $A$, and is constantly $1$ there.

If we wanted to be more pedantic, "computing a function step by step" is not completely precise. One usually takes a "program" implementing the semi-characteristic (e.g. a Turing machine accepting each element of $A$, and diverging elsewhere) and executes that program step-by-step.

So, given two TMs $M$ and $N$ implementing both semi-characteristics, you can craft a new TM $O$ which runs them "in parallel, step by step" on the same input $w$. Eventually, one (and only one) of them will halt, and $O$ can accept or reject "w" consequently.

A completely computational-model-agnostic way to state "computing step by step" could be to exploit the Kleene's normal form theorem, where a number $x$ plays an equivalent role to the number of steps. While this is arguably the "true mathematical" way to do it, in computer science we often prefer to work with "programs" (TMs,...) since we find those more familiar.


Number of comparisons in Binary search I know this question is very trivial to ask, but I have got some doubt
while solving this problem.Code is given below

public class BinarySearch {
public static int binSearch(int a[], int x) { // a is sorted
int low = 0, high = a.length - 1;
while (low <= high) {
 int mid = (low + high) / 2;
 if (x < a[mid])
 high = mid - 1;
 else if (x > a[mid])
 low = mid + 1;
 else
 return mid;

}

return Integer.MIN_VALUE;

}

If we want to calculate the worst case comparisons of binary search,then

it will be $2 \log n+1$, because $\log n+1$ for checking (low<=high) and $\log n$ for (x < a[mid]) or if (x > a[mid]).

Alright , i have no issue here , i can happily say that worst case comparison for Binary search is $2\log n +1$

I faced issue when i tried to solve the recurrence equation, given as-:

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

  $\text{Base Case}\,\,T(1)=1$

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

Generalizing the equation i got-:

$T(n)=T(\frac{n}{2^{k}})+1+1..+1(k \text{times})$

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

  $\frac{n}{2^k}=1$

  $k=\log n$

So $T(n)=\log n+1$
What actually this value signifies?
Is it Minimum number of comparison?
Confused
Please help me out

The recurrence is supposed to express the worst-case runtime of binary search on an input of size $n$ (the letter $T$ might stand for time). The range you have to search search is halved in each step, so you get the $T(n/2)$ term on the right side.

Most of the time people only count the comparisons of the data, not the extra comparison for the loop condition, so it takes 1 comparison to halve the search space. For your analysis you might want to write a $+2$ instead of the $+1$, since you do count the loop condition.

As we want to express the worst case runtime, we assume that the element is not in the array, so the recursion terminates only when there is just one element left. This provides us with the base case of $T(1)=1$.


Efficient algorithm to translate/shift polynomials I have a polynomial $P(x)$, and given some constant $d$, I need to find the polynomial $P(x+d)$. For example, if $P(x)=x^2$ and $d=1$, then the result would be $P(x+1)=(x+1)^2=x^2+2x+1$ (with the coefficients stored in an array/vector).

I know the algorithm with $O(n^2)$ time complexity, which is based on Horner's method: $$a_0+(x+d)(a_1+(x+d)(a_2+...+(x+d)a_n))$$
However, it is not efficient enough for my needs. Is there an algorithm that is more efficient for solving this problem?

P.S. The coefficients and $d$ will always be integers, if that helps.

Use FFT. Suppose that $\deg P \leq n$ and we use FFT on $n$ points (usually $n$ would be the smallest power of 2 which is at least $\deg P$). Let $\omega$ be an $n$th root of unity. The Fourier coefficients of $Q(x)
= P(x+d)$ are
$$
\hat{Q}(m) = \sum_{i=0}^{n-1} Q(i) \omega^{mi} = \sum_{i=0}^{n-1} P(i+d) \omega^{mi} = \sum_{i=0}^{n-1} P(i) \omega^{m(i-d)} = \omega^{-md} \hat{P}(m).
$$
This shows how to compute the Fourier transform of $Q$ from that of $P$ in linear time. Since FFT takes time $O(n\log n)$ (for suitable $n$), the overall running time is $O(n\log n)$. Choosing $n$ as indicated above, this becomes $O(\deg P \log \deg P)$.


Faults in the halting problem reasoning I find very interesting the problem of existence of a machine $H$ which given as input any algorithm $P$ outputs whether $P$ halts or not. Alan Turing disproved the existence of such an $H$ machine in the following way:
"Assume $H$ exists. The input of $H$ is any algorithm $P$. The output of $H$ is $YES$ if $P$ halts and $NO$ if $P$ doesn't. Create another machine $N$ with input in the set $\{YES,NO\}$ and without output. The machine $N$ does this: if the input is $YES \to \text{loop for ever}$ otherwise, if input is $NO \to \text{halt}$. Let us call the composition of $H$ followed by $N$ as $X$. We will simply write $X(P) = N(H(P))$. Now $X$ has as input a machine and no output (it either halts or loops forever). What Turing does is to "feed" $X$ with itself ... and reason as follows: if $X(X)$ halts then $X(X) = N(H(X)) = N(YES) = \text{loops for ever}$ from which somehow the contradiction arises ..." but here one should assume (in order to obtain a contradiction) that $X(X) = X$ ...
Question
I do not know why such an assumption, $X = X(X)$ would be made. In fact, in my opinion, $X \neq X(X)$ for any input $P$ (that is all Turing is proving actually). Indeed assume $P$ is a machine which halts (runs for ever). Then $X(P)$ does not halt (does halt) when $X(X(P))$ does (does not). I do not understand therefore, why $H$ cannot exist! Where is my mistake ?

The proof you wrote in the question is faulty, because it uses the wrong definition of the Halting oracle. You tried to fix the proof by inserting the assumption $X(X) = X$, but that is not the way to do it. Here is the correct proof.
Definition: A halting oracle is a machine $H$ which takes as input a pair  $(M,I)$ where $M$ is the (description of) a machine and $I$ an input. $H$ always  halts and outputs:

"yes" if $M(I)$ halts,
"no" if $M(I)$ does not halt.

Theorem: A halting oracle does not exist.
Proof. Suppose $H$ exists. We shall derive a contradiction.
Let $N$ be a machine which does the following upon receiving an input $I$:

if $I$ is "yes" then $N$ loops forever,
otherwise $N$ halts.

Let $X$ be the machine which takes an input $I$ and then acts as $N(H(I, I))$. We now prove two contradictory facts:

$X(X)$ does not halt.
$X(X)$ halts.

To prove the first claim, suppose $X(X)$ halts. Then $H(X,X)$ outputs "yes", therefore $X(X) = N(H(X,X)) = N(\text{yes})$, but $N(\text{yes})$ does not halt. Therefore it is not true that $X(X)$ halts.
To prove the second claim, suppose $X(X)$ does not halt. Then $H(X,X)$ outputs "no", therefore $X(X) = N(H(X,X)) = N(\text{no})$, but $N(\text{no})$ halts. Therefore it is not true that $X(X)$ does not halt, so it halts. $\Box$.


Is the MinMax/optimization/search variant of a decision problem always easier/equal? Is the MinMax/optimization/search variant of a decision problem always easier/equal in complexity because we can always reduce them to their decision variant?

From Wikipedia:

  If the longest path problem could be solved in polynomial time, it could be used to solve this decision problem, by finding a longest path and then comparing its length to the number k. Therefore, the longest path problem is NP-hard. It is not NP-complete, because it is not a decision problem.

Is the max-variant of this problem only NP-hard because the decision-variant is also NP-hard (and NP-complete)? (and not because it is harder)

What about polynomial time problems? If the decision variant of a problem is in P, I would assume that the optimization variant is not NP-hard, because that would imply P = NP. Do we say that it is in P then, or is it in another class/no class?

No.  A reduction only proves that it is "at least as hard", not that it is easier.  Normally, the optimization problem is approximately as hard as the corresponding decision version (to within a polynomial factor).

If the decision problem is in P (can be solved in polynomial time), and there's a polynomial time reduction from the optimization problem to the decision problem, then that implies that the optimization problem can be solved in polynomial time.  It's not literally in P, because P is a class of decision problems, but you can think of it as being in some class that is analogous/similar to P.

It's not clear to me what you mean by "the MinMax variant" or "the max-variant", so I can't answer that part.


Are 'zero-one' jigsaw puzzles NP-complete? I'm interested in a slight variant of tiling, the 'jigsaw' puzzle: each edge of a (square) tile is labeled with a symbol from $\{1\ldots n, \bar{1}\ldots\bar{n}\}$, and two tiles can be placed adjacent to each other iff the symbol on one tile's facing edge is $k$ and the symbol on the other tile's facing edge is $\bar{k}$, for some $k\in\{1\ldots n\}$.  Then, given a set of $m^2$ tiles, can they be placed into an $m\times m$ square (rotating but not flipping the tiles) with all edges matching correctly?  (There's also a variant on this problem in which four $1\times m$ 'framing' edges are provided and the pieces must fit correctly into that frame).

I know this problem is NP-complete for sufficiently large $n$, but the bounds that I've seen on $n$ seem to be fairly large; I'm interested in the problem for small values of $n$ and in particular for $n=1$, the 'zero-one' case (where every edge is labeled either $0$ or $1$ and edges with a $0$ must be matched to edges with a $1$).  Here there are (with rotational symmetry) just six tile types (the all-zeroes tile, the all-ones tile, the tile with three zeroes and a one, the tile with three ones and a zero, and two distinct tiles with two zeroes and two ones, '0011' and '0101'), so a problem instance is just a specification of $m$ and a set of five numbers $T_{0000}$, $T_{0001}$, $T_{0011}$, $T_{0101}$, $T_{0111}$ and $T_{1111}$ (representing the count of each type of tile) with $T_{0000}+T_{0001}+T_{0011}+T_{0101}+T_{0111}+T_{1111}=m^2$.  The problem is obviously in NP (with $m$ given in unary) since a solution can simply be exhibited and then checked in polynomial (in $m$) time, but is it known to be NP-complete, or is there some dynamic programming algorithm that can be applied here?  What about the 'framed' case where the problem specification also includes the four edges of the square that are to be matched?  (Obviously if the unframed case is NP-complete the framed case almost certainly is as well)

Since you mentioned you are interested in solving this problem for small values of $n$, I would suggest that you try implementing this in a SAT solver or as an integer linear program (ILP).  Either one will be able to encode the constraints, but in a slightly different way:

For SAT, there is a very clean encoding of the choice of which tile goes into each square, and a slightly less clean encoding of the constraint regarding the number of each kind of tile (using bit arithmetic).
For ILP, there is a very clean encoding of the constraint regarding the number of each kind of tile available, and a slightly less clean encoding of the constraints on which tiles can be adjacent to each other (but it is still expressible, since you can express arbitrary boolean formulas in ILP).

I would expect that for small or medium sized $n$, this approach might work efficiently.


Find which vertices to delete from graph to get smallest largest component Given a graph $G = (V, E)$, find $k$ vertices $\{v^*_1,\dots,v^*_k\}$, which removal would result in a graph with smallest largest component.

I assume for large $n = |V|$ and large $k$ the problem is difficult (NP-hard), but I am interested in small values of $k$ ($k \in \{1, 2, 3, 4\}$).

For $k = 1$, I think it is possible to find best vertex $\{v^*_1\}$ to remove by performing single depth-first-search of the graph (i.e., checking articulation points).

For $k = 2$, it would be possible to find best vertices $\{v^*_1, v^*_2\}$ by performing $n$ depth-first searches (each of them for graph $G_i = G / \{v_i\}$). A similar approach could be applied in the case $k > 2$.

I wonder if there is any better solution than that.

(Related: counting the minimum number of vertices without necessarily enumerating them)

The problem you are describing is known as Component Order Connectivity in the field of vulnerability measures of graphs.  The decision version of the problem is as follows:

  Component Order Connectivity:

  Input:  Graph $G = (V,E)$, integers $k$ and $\ell$

  Question: Does there exist a set of vertices $X \subseteq V$ of size at most $k$ such that the size of the largest component of $G - X$ is at most $\ell$?

The problem is obviously NP-complete since it generalizes vertex cover; the case when $\ell=1$ is vertex cover.  Hence the problem cannot be fixed parameter tractable when parameterized by $\ell$ (unless $FPT = W[1]$).  The problem is also known to be $W[1]$-hard when parameterized by $k$.  Hence, we have to resort to algorithms with an exponential running time in $k+\ell$.

Very interesting question.  For input $G,k,\ell$, a brute force approach would be:

branching(G,k,l):
    Find a connected set of vertices D of G of size l+1
    if no such D exists:
            return True // no component of size > l
    for v in D:
        if branching(G-v,k-1,l):
            return True
    return False

The algorithm runs in time $(\ell + 1)^k \cdot n^2$.

Observe that any yes instance $G,k,\ell$ of the problem has treewidth, and indeed pathwidth at most $k+\ell$.  This can be observed by seeing that taking a deletion set $X$ of size at most $k$ yields a graph $G-X$ where every connected component has size at most $\ell$.  Hence, a valid path decomposition is simply to construct one bag for each of the components in $G-X$ and then add all of $X$ to every bag.  It follows that any yes instance has $|E(G)| \leq n(k+\ell)$.

A related problem has been studied in the past under the name Graph Integrity, or Vertex Integrity to distinguish the vertex deletion version and the edge deletion version:

  Vertex Integrity:

  Input:  Graph $G = (V,E)$, integer $p$

  Question: Does there exist a set of vertices $X \subseteq V$ such that $|X| + \max_{D \in cc(G-X)}|D| \leq p$?

That is, the sum of the deletion set and the size of the maximal component should be minimized.  This problem is also NP-hard.  See, e.g.,

Clark, L.H., Entringer, R.C., Fellows, M.R.: Computational complexity of integrity. J. Combin. Math. Combin. Comput 2, 179–191 (1987)
Fellows, M., Stueckle, S.: The immersion order, forbidden subgraphs and the complexity of network integrity. J. Combin. Math. Combin. Comput 6, 23–32 (1989)


Memory Mapping Segment I read that "Memory Mapping Segment"/"memory mapped file" is a segment of the virtual memory of a process, where a file or file-like Ressource is loaded into. It is for high performance file I/O.

I wonder..

(1) Is this normally done automatically by the OS?

(2) What are reasons to do this other than loading shared libraries? I can imagine that bigger files quickly blast the address space..

(3) if this isn't done, then where is the file read from. Does the process have to contact the hard drive to get the information from the library if it is not a "memory mapped file"

1) Yes, for OSes that support memory-mapped files. The OS simply allocates a region of the virtual address space for the file, and sets up its paging algorithms so that,

when a page is accessed but is not in RAM, it is loaded in RAM
when there's little RAM left, some memory-mapped pages can be saved to disk and freed (they can be reloaded later on, if needed, from disk)

This is very similar to what happens with swapping.

2) On 64 bit systems, I'd say that virtual address space is a non-issue. Even with files as ridiculously large as 1PB=1024TB each, you'd have to map 16000+ of them to exhaust the space. Even if some address space is reserved by the OS, this limitation is irrelevant until we can store petabytes very easily.

On 32-bit systems, yes, that can be an issue.

For a possible reason: read-only memory-mapped segments are cheap. The OS can unload their pages when memory becomes too tight, without accessing the disk. If the process used regular memory the access would be less efficient, unless the process implements some memory-management itself. The process is simpler to design since it can exploit the OS for making access efficient, and pretend a large file was fully loaded in RAM, roughly.

Read-write memory-mapped segments are less useful, in my opinion, but those are also simple to use by the process.

3) the file is read from (and written to, if the mapped segment isn't read-only) disk. But this is done by the OS, in its paging routines, not by the process.


Prove or disprove the given equivalence f(n) = n/100 = Ω(n) . I am new at proving asymptotic notations , especially at big-Ω. That's why I even didnt start the beginning myself.  I tried to prove myself as looking at other proofs and searched on the internet to find same question but I couldnt find. I dont think so this question is a duplicate of another which was asked here. Thanks for helps.

I assume $n$ takes only positive values. By the definition of Big-Omega you could prove it by showing the following

$$\lim_{n \rightarrow \infty}\frac{\frac{n}{100}}{n} >0$$

The rest is a simple exercise.


Check a variable within a range with a binary variable I have a value, a, it can be any value from 0 to 1. In an integer linear program, how can I formulate a constraint that uses a binary variable, y, to determine whether a is within a range of 0 and 1 or not.

Thanks

If I understand corectly, you want to formulate a system of linear constraints on a real variable $a$ and a $\{0,1\}$-variable $y$
such that the solutions are given by
$$[0,1]\times\{1\} \bigcup [1,\infty)\times \{0\}.$$

This is impossible.  No linear constraint can put an upper bound on $a$ for some values of $y$ without putting an upper bound on $a$ for all values of $y$.

You can, however, just split the problem into two pieces and solve each one separately.


Why don't we use quick sort on a linked list? Quick sort algorithm can be divided into following steps

Identify pivot.
Partition the linked list based on pivot.
Divide the linked list recursively into 2 parts.

Now, if I always choose last element as pivot, then identifying the pivot element (1st step) takes $\mathcal O(n)$ time.

After identifying the pivot element, we can store its data and compare it with all other elements to identify the correct partition point (2nd step). Each comparison will take $\mathcal O(1)$ time as we store the pivot data and each swap takes $\mathcal O(1)$ time. So in total it takes $\mathcal O(n)$ time for $n$ elements.

So the recurrence relation is:

$T(n) = 2T(n/2) + n$ which is $\mathcal O(n \log n)$ which is the same as in merge sort with a linked list.

So why is merge sort preferred over quick sort for linked lists?

The memory access pattern in Quicksort is random, also the out-of-the-box implementation is in-place, so it uses many swaps if cells to achieve ordered result.
At the same time the merge sort is external, it requires additional array to return ordered result. In array it means additional space overhead, in the case if linked list, it is possible to pull value out and start merging nodes. The access is more sequential in nature.

Because of this, the quicksort is not natural choice for linked list while merge sort takes great advantage.

The Landau notation might (more or less, because Quicksort is still $\mathcal O(n^2)$) agree, but the constant is far higher.

In the average case both algorithms are in $\mathcal O(n\log n)$ so the asymptotic case is the same, but preference is strictly due to hidden constant and sometimes the stability is the issue (quicksort is inherently unstable, mergsort is stable).


Find which bundles can be demanded together This question comes from economics. There is a market $M$ that contains $m$ items. There is a value function $v:2^M\to \mathbb{R}$, that assigns a monetary value to each "bundle" (- subset of $M$). The function is given by $2^m$ values - a value per bundle.

A price-vector $p$ is a vector that assigns to each item $x\in M$ a non-negative price $p_x$. Given a price-vector, the net utility of a bundle is its value minus its price, i.e:

$$ u(X) = v(X) - \sum_{x\in X}p_x$$

A bundle is called demanded if its net-utility is maximal - no bundle has larger net-utility.

A pair of bundles is called a demand-pair if there exists a price-vector such that both of these bundles are demanded (i.e, they have the same net-utility and it is maximal).

I am looking for an algorithm that receives the valuation $v$ and finds all demand-pairs.

For example, suppose there are $m=2$ items and the valuation function is:

$v(\emptyset)=0$, $v(\{x\})=2$, $v(\{y\})=3$, $v(\{x,y\})=4$.

Then:

$\{y\}$ and $\{x,y\}$ are demand-pairs, because when $p_x=1,p_y=0$, both these bundles have net-utility 3, which is maximal.
$\{\emptyset\}$ and $\{x,y\}$ are not demand-pairs, because if they have the same net-utility, then this utility must be 0. Then, necessarily $p_x+p_y=5$; but then either $p_x<2$ or $p_y<3$; but then either $\{x\}$ or $\{y\}$ (or both) have a net-utility of more than 0, so $\emptyset$ is not demanded.

This can be solved in polynomial time, by solving $2^{2m}$ linear programs.  (That might look exponential, but is polynomial in the size of the input, as the input size is $2^m$.)

Given a pair of bundles, you can check whether it is a demand-pair using linear programming; see below.  So, you can apply this to all candidate pairs.

Suppose we have two bundles, $X,Y$, and we want to know if they are a demand-pair.  Introduce a variable $p_x$ for each $x \in M$.  It's easy to write a linear equality that expresses that $X,Y$ have the same net-utility: $u(X)=u(Y)$.  Also, it's easy to write linear inequalities to express that no other bundle has higher net-utility: $u(X) \ge u(Z)$ for all other bundles $Z$.  Each of those is a linear (in)equality on the variables $p_x$.  We also have the inequalities $p_x \ge 0$.  Now use linear programming to test whether all of those inequalities are simultaneously satisfiable; if they are, there exists a price-vector where $X,Y$ are simultaneously demanded.

As an optimization, note that $X,Y$ are a demand-pair for market $M$ iff they are a demand-pair for market $X \cup Y$: without loss of generality you can set the price of every item in $(X \cup Y) \setminus M$ to $+\infty$.  Also, without loss of generality you can set the price of every item in $X \cap Y$ to 0.  Consequently, $X,Y$ is a demand-pair for market $M$ iff $X'=X \setminus Y$ and $Y'=Y \setminus X$ are a demand-pair for market $X' \cup Y'$.  This will make each linear program smaller and more efficient to solve.  It also means that you only need to test pairs that have no common intersection, so it suffices to test at most $3^m$ pairs $X',Y'$.


Runtime analysis with recursion factor I have this code:

if n is even
{
for i=1....n
   for j=1...i
      print j
return 8*foo(n/2)
}

Asking to calculate the running time $T (n)$. I thought at first that I can write the function like this:

$$T(n)= 8T(n / 2)+n^2$$
But according to the answers of the quiz, they are saying that the function looks like this:

$$T (n)= T(n / 2)+n^2$$
Why we can delete 8? Thank you very much!

You're asked to calculate the running time of the segment, not the value returned. In terms of running time, multiplication by 8 is a single operation, so the running time is (roughly) $T(n)=T(n/2)+n^2$.


CNF H is in the class P CNF H = {<ø>|ø is a satisfiable cnf-formula where each clause contains any number of
literals, but at most one negated literal}

I want to show that CNF H is in P, but I'm having some trouble finding an algorithm. My first idea was to check for each clause c in P if that clause contained at most one negated literal. If no clause contains more than one negated literal, accept, if not, reject.

The problem with this idea is if there is a clause with only one literal, and this literal is negated. Than the clause would be false, and therefore ø is false. How do I write an algorithm that also covers this case?

I have come up with a polynomial-time algorithm for this language that I think is in P.

Possible algorithm (-x means not x).

M = "on input <ø> where ø is a boolean formula in CNF:
1. Repeat until there are no (-x) unit clauses:
   For a unit clause (-x), remove all the clauses containing -x from ø
     and remove all occurrences of x from the clauses in ø
2. If there is an empty clause in ø, reject.
3. Let all literals x in ø be 1, -x 0, and accept.


Does the concept of the array pre-date physical computer memory implementations? Does the concept of the array (a sequence of equally-sized elements accessible in O(1) time, occupying O(n) space) pre-date physical computer memory implementations?

I am trying to gauge whether computer memories were designed for the array or whether the array concept was designed to work with computer memories.

Here's a thought. Consider the venerable spreadsheet. No, not the program, but the piece of paper. It was a regular array of cells, with column and row check sums and corner balancing for verification. They were used to hold accounting data back in the days when this was done by hand.

While not data in memory, it does embody the concept of a regular array of data.

I can't find a date on the use of paper spreadsheets, but I did find this:

  However, the spreadsheet has been in existence, as a paper based
  product, for longer than any of the computer based products. In the UK
  it was called “Multi-column analysis paper”. In the USA it was called
  a “spreadsheet” hence the name of the computer based version.

http://www.bygsoftware.com/Excel/Standards/SS_801_spreadsheetsbriefhistory.htm


In the reduction from HALT to ALLHALT, why does the constructed Turing machine loop indefinitely when the inputted Turing machine rejects? Let HALT be the language $\{\langle M, w\rangle : M\text{ is a TM that halts on }w \}$. Let ALLHALT be the language $\{\langle M\rangle : M\text{ is a TM that halts on all inputs}\}$. Use a reduction from HALT to show that ALLHALT is not decidable.

Online (link) I found this (simular) solution:

  $D$ = on input $s$:

  Check that $s$ is of the form $\langle M, w\rangle$, where $M$ is a Turing machine and $w$ is a string over the input alphabet of $M$. If not, reject $s$.
  Otherwise continue.
  Define a new machine $M_2$ corresponding to the pair $M, w$ as follows.

  $M_2$ = on input $v$:

  If $v$ is not the same as $w$, halt. Otherwise continue.
  Feed $v$ (meaning $w$ in this case) to $M$ and let $M$ compute on $w$.
  If $M$'s computation on input $w$ halts and rejects $w$, loop
  indefinitely. If $M$'s computation on input $w$ halts and accepts $w$,
  halt. Otherwise continue looping like $M$ is doing.

  Notice that we've designed $M_2$ in a clever way so that the result of
  $M$'s computation on input $w$ is encoded in the halting behavior of $M_2$.
  Namely, $M$ accepts $w$ if and only if $M_2$ halts on all inputs. In terms of
  language membership, this means that $\langle M, w\rangle$ belongs to Halt if and only if $\langle M_2\rangle$ belongs to Halt2. In light of this fact, finish the description of $D$'s computation as follows.

  Feed the string $\langle M_2\rangle$ into the decider $D_2$.
  Return $D_2$'s decision.

I don't understad the point 3: If $M$'s computation on input $w$ halts and rejects $w$, loop indefinitely. Why does $M_2$ need to loop indefinitely?

Because the problem HALT defined in the online source is different from yours. Their HALT is defined as:

\begin{align}
\{ \langle M, w\rangle \mid{} &M\text{ is a Turing machine, $w$ is a string,}\\
&\text{and $M$ }accepts\text{ $w$ after a finite computation}\}
\end{align}


Is writing a number as two squares and writing the factors of a number equally hard? Let $L_1$ and $L_2$ be the following:

$L_1=\{r:\exists x,y \in \mathbb{Z} \text{ such that } x^2+y^2=r\}$

$L_2=\{(N,M): M<N,  \exists 1<d\leq M \text{ such that d|N} \}$

Claim $L_1 \leq_P L_2$

Sketch Proof

If I want to know whether $r\in L_1$.

The number of integer solutions to $x^2+y^2=r$ is given by

$g(r)=\sum_{d|r}{\chi{(d)}}$ where $\chi (x)=sin(\frac{\pi x}{2})=\cases{ 1\text{ when }x\cong 1 \text{ mod }4 \\ -1 \text{ when }x\cong 3 \text{ mod }4 \\ 0 \text{ when } 2|x }$

Then $L_1=\{r: g(r)\neq 0\}$. So then to answer is "$r\in L_1$?" is at most as hard to answer as "what are the divisors of $r$?"

$\square$

What I would like to know is if this is true the other way around. Is it true that if I had a machine which could tell me in constant time whether $r\in L_1$ could I create a machine which could answer "is $(M,N)\in L_2$?" in polynomial time?

Motivations

This question came out of a discussion on this question.

Apologies
I am really just a math.se member who has gotten lost and wandered on to cs.se. Let me know if my question is clear and up to the standards of this site. I am happy to make corrections.

Here's the situation as far as I can tell:

The most efficient way known to test membership in $L_1$ is to factor $r$.  No more efficient algorithm seems to be known.

However, there is no obvious reduction to prove $L_2 \le_P L_1$.  In other words, if we had a machine to decide $L_1$, there's no easy way to use that to factorize.  If we want to factor a number $N$, we can check whether $N \in L_1$, but this only gives us one bit of information about the factors of $N$.  Testing multiples of $N$ (i.e., whether $cN \in L_1$ for some integer $c$) doesn't give us any additional information, as knowing whether $N \in L_1$ suffices to predict whether $cN \in L_1$ for all $c>0$.  Testing other numbers doesn't seem to help in any obvious way, either. (Testing whether $N' \in L_1$ for some other number $N'$ doesn't seem to give any useful information, if $\gcd(N,N') =1$; and if we had a way to find another number $N'$ such that $\gcd(N,N')\ne 1$, we'd already know how to factor, but of course we don't know how to do that -- so any number we know how to generate is unlikely to give us any useful information on the factors of $N$.)  This is not a proof; it is just handwavy intuition.

So it seems plausible that $L_1$ might be easier than $L_2$, and it also seems plausible that they might be of the same difficulty.  I'm not aware of any further results on this subject.


Algorithm to determine if a number is perfect on a Turing Machine I've been trying for a while now to find a solution for the problem in the title: determining if a number is perfect using a Turing Machine. I only had one class on the TM and while I did "get" how it works, this particular algorithm is being really hard for me to develop.

The algorithm I'm trying to implement on the TM is basically this (on C, returns true iff n is a perfect number):

int main(int n) {
  int i=1, sum=0;

  while ( n > i ) {
    if ( n % i == 0 ) {
      sum = sum + i;
    }
    i++;
  }

  return sum == n
}

The tough part for me right now is the while(n>i) loop and the n%i inside it.

Since I already have a program that does a%b, I was trying to build the TM graph around it, but I'm not sure it's the best idea, specially since the b on this case changes on every iteration. The software I'm using to simulate the TM is called JFlap.

The algorithm on table or graph form would be perfect.

You need do do:

Factor the number given
Add up the factors, and check they add up to $n$

It should be something like:

sum = 0;
for(k = 1; k < n; k++) {
     if(n % k == 0)
         sum += k;
}
return sum == n;

To get n % k == 0 you can:

tmp = n;
while(tmp > 0)
    tmp -= k;
return tmp == 0;

Translating into TM-speak and splicing all this together isn't hard, just very tedious. Use a multitape TM to simplify your description.


What is a monotone dataset and monotone classification? Classification algorithms, such as k-Nearest Neighbors, are well known in machine learning area, but I faced this new expression Monotone classification and I wonder what does it stand for.

I guess that it has something to do with some peculiar characteristic of the dataset, e.g. if all the objects have growing attributes and, plotted in a 2D plane, they look as if they were gathered around the line of the function f(x) = x or something like this, but as english is not my native language, I couldn't understand the raw meaning of Monotone and Monotone classifiers, the things I read were so confusing that I don't think it is worth it to mention.

I read this:

  The evaluation of teaching courses based on surveys gathered from
  students’ opinions can be categorized as a monotonic classification
  problem if it intends to predict a final qualification that summarizes
  the general quality of the course. The students are asked to evaluate
  each course according to several aspects related to interest,
  achieving appropriate class participation, teaching resources,
  capabilities of the teacher, etc.

I would like to be able to say why these surveys behave as a monotone dataset, but no explanation fits what I have in mind about the monotone definition.

A monotone classifier is a classifier that is a monotonic function.

One reasonable definition of monotone data set is that it is a data set that is consistent with some monotone model (i.e., where there exists a monotone classifier that gets 100% accuracy).  I don't know if this is a standard definition so hopefully any text that uses that phrase would provide a definition.

Why use a monotone classifier in the setting you mention? Perhaps we have some a priori reason for believing that, all else being equal, the higher the students rate their satisfaction, the higher the quality of the course.  That amounts to a monotonicity assumption about the underlying model that relates quality to satisfaction.  If we assume that the data was generated from a monotone model, it is reasonable to try to learn a monotone classifier.  Whether this is appropriate in any particular setting depends on whether you have a reason to think that the data does come from a monotone process/model or not.


If a DFA were implemented as a circuit, what would the empty string correspond to as input? Say we have a DFA like the one shown below that accepts the empty string, $\varepsilon$.

Also suppose the functionality of this DFA has been implemented as a circuit so that an led lights up whenever an accepted word is detected as input.

While this hypothetical circuit is "idle", i.e. not receiving any a's or b's as input, is the led on? Is it appropriate to think of $\varepsilon$ as idling without real input? Is that what $\varepsilon$, an input string of length zero, represents?

As a follow up, for a circuit implementation of the next DFA, would it have an led that never turns on even while idle?

Deterministic automata over finite words (DFAs) that accept or reject a given word can be seen as finite-state machines that read elements from some alphabet $\Sigma$ and output elements from the output alphabet $\mathbb{B}$ that represent whether the word read so far is accepted by the original DFA.

Translating such finite-state machines to circuits is a classical topic in technical computer science. For instance, you could assign a bit-vector of the same length to every state and then use the Espresso logic minimizer to compute a relatively efficient circuit. Note that such circuits have memory.

Such finite-state machine come in two variants: Mealy and Moore machines. Both of them operate in discrete steps. At every step of their computation, Mealy machines first read an input character and them produce an output character. For Moore machines, it is the other way around: they first produce their output character and then read the next input character.

The answer to your question now depends on which model you use: If you translate your DFA into Moore machine form, the machine first outputs whether the word seen so far is accepted and only then looks at the next character. In the first step of its computation, it thus outputs whether the empty word is accepted. Mealy machines read the respective next character in every step and only then produce the next output. Thus, whether the empty word is accepted by the original DFA cannot be observed when looking at a run of the Mealy machine (unless you do the translation in a way that the machine always delays its output by one step, which normally increases the number of states by a factor of at most two).

The model that Yuval Filmus was referring to in his comments is one that is used in circuit complexity. There, it is looked at how large circuits need to be that categorize inputs of a fixed length into accepted and non-accepted ones. The characters of the input words are all read at the same time in this model and the circuits do not have memory.


Most cost effective way to traverse a set path I have a set path of $N$ destinations to be visited in order, knowing the distance $D_i$ between each one of them. I can traverse one node $i$ with the cost of $D_i \times r$ or traverse any $5$ nodes in order with a set cost of $B$. How can I find the most cost effective way to visit all the destinations using dynamic programming?

Let us number the destinations from $1$ to $N$ and define an array $c[N]$ where $c[i]$ is the minimum cost to travel to destination $1 \leq i \leq N$. We wish to calculate $c[N]$.

It is clear that $c[1] = D_1 \times r$, because if we find ourselves at destination $1$ we can only have gotten there by travelling one destination at a time, instead of travelling five destinations at a time.

The minimum cost of travelling to destination $2$ must be $c[2] = D_2 \times r + c[1]$ for identical reasons ($2 < 5$) as before. We add the minimum cost of reaching destination $1$ to the minimum cost of reaching destination $2$ because we must have travelled from destination $1$ to $2$.

Now we see that for destinations $i \geq 5$, that we could have reached them by travelling through five destinations at a time instead of the previous one destination at a time. This means
$$c[i] = \min(B + c[i - 5], D_{i} \times r + c[i - 1])$$

Where $c[0] = 0$. From this pattern, we can calculate $c[N]$ in $O(N)$ time complexity.


Does it make sense to talk about the complexity of non-computable functions (such as the Halting problem)? I have seen numerous proofs (such as this) that the Halting problem is in the class of NP. However, the Halting problem is non-computable.

Does it make sense to discuss the complexity of computing a function that cannot be computed?

Computational complexity studies the computational resources required to decide problems in some particular model of computation. Because of this, it makes no sense to talk about the complexity of a problem that is not computable in the model of computation you're talking about.  Or, to put it the other way around, it only makes sense to talk about the computational complexity of the halting problem with respect to models of computation in which that problem is computable.  For example, you could talk about the complexity of recursively enumerable problems using Turing machines with an oracle for the halting problem as your model of computation.

The proof you link to does not show that the halting problem is in NP. It shows that the halting problem is NP-hard, which just means that every problem in NP is polynomial-time reducible to the halting problem.


Vector clock :why Singhal Kshemkalyani differential technique require FIFO for message passing? Singhal–Kshemkalyani’s differential technique is based on the
  observation that between successive message sends to the same process,
  only a few entries of the vector clock at the sender process are
  likely to change. This is more likely when the number of processes is
  large because only a few of them will interact frequently by passing
  messages. In this technique, when a process  Pi sends a message to a
  process Pj , it piggybacks only those entries of its vector clock that
  differ since the last message sent to Pj.

I am understanding above but not the following statement

  this technique requires that the communication channels follow FIFO
  discipline for message delivery.
  link

Chapter 3 -Logical clock from above book and sub topic is Efficient implementations of vector clocks

Thanks lot.

All it's saying is that the messages between two processes need to be received in the order they are sent. If I'm going to send only differences between the previous message, we both better agree on what "the previous message" is.

For example, if I send "increment the first and second component" and then "increment the first and third component" but you receive them in the opposite order, you are likely to make form incorrect assumptions about how these messages relate to messages you're receiving from other processes. The correct intermediate state will have a vector clock that looks like $(1,1,0)$ but the one you'd reconstruct from the out of order messages is $(1,0,1)$. A message from another process with vector clock $(2,0,1)$ might then look like its strictly after the out-of-order message when, in fact, it is concurrent with it.


Where does the FLP impossibility proof depend on allowing a single process failure? Question
I'm reading the FLP impossibility paper.
I think I understand the idea of the proof, and I don't have questions about it.
However, it seems like the assumption of having at most, a single faulty process is not used in the proof.
Put another way, if we remove this assumption and forbid process failure, the proof still seems to hold.
This can't be correct, because then it wouldn't be possible to construct a protocol that succeeds with no faulty processes.
However, it is possible, and a protocol meeting this criterion is supplied in section 4.
My question is therefore: which part of the proof relies on the condition that one process can fail?
My best effort at an answer
Definitions
For reference, the assumption in question appears in the definition below:

A run is admissible provided that at most one process is
faulty and that all messages sent to nonfaulty processes are eventually received.

Also relevant is the definition of a deciding run:

A run is a deciding run provided that some process reaches a decision state in
that run.

I'll also use my own definition, below:

A run is 0-admissible provided that no processes are faulty and that all messages sent to nonfaulty processes are eventually received.

Approach
I want to show that, by changing the definition of admissible to that of 0-admissible, the proof is no longer correct. Therefore, it would rely on the at most one failure part of the admissible assumption.
Lemma 2
Lemma 2 ("P has a bivalent initial configuration") references this assumption. In particular:
$C_0$ and $C_1$ are $0$-valent and $1$-valent initial configurations, respectively. They differ only in the initial value $x_p$, of a single process $p$.

Now consider some admissible deciding run from $C_O$ in which process $p$ takes no steps, and let $\sigma$ be the associated schedule.
Then $\sigma$ can be applied to $C_1$, also, and corresponding configurations in the two runs are identical except for the internal state of process $p$. It is easily shown that both runs eventually reach the same decision value. If the value is $1$, then $C_0$ is bivalent; otherwise, $C_1$ is bivalent.

Both cases above being a contradiction, proving the lemma.
Replacing admissible with 0-admissible in Lemma 2
I'd hoped that replacing admissible with 0-admissible would show the proof no longer works.
For simplicity, I'll only consider the case where $N = 2$.
Now consider the (modified) line of the proof:

Now consider some 0-admissible deciding run from $C_O$ in which process $p$ takes no steps.

0-admissibility implies the following:

Process $p$ cannot be faulty
Process $p$ must have received all messages sent to it
A decision state is reached

By non-triviality, the schedule $\sigma$ must not initially be in a deciding state.
Now, we know from (1) and (2) that no messages can have been sent to process $p$: Either it would have taken steps to receive them (violates assumptions), or it didn't receive them (violates 0-admissibility).
Therefore, we can ignore process $p$ and focus on the remaining process. I had assumed that it being deterministic implies the configuration must be univalent, but I can see a problem.
Namely, the deterministic process can introduce nondeterminism by sending a message to itself, and measuring the time taken to receive it. This effectively generates a random integer, which can be used to randomly choose an answer.
Even if it were right, this seems like a very complex answer to a simple question - have I missed something obvious? Is there another part of the proof where the assumption of faultiness is required more explicitly?

The part of the original paper's proof that requires node failure to prove the impossibility is case 2 of lemma 3. This case assumes that there is a "finite deciding run from C0 in which p takes no steps". p taking no step means it has died/failed.

From case 1 of lemma 3, we know that there exists a pair of messages, called e and e' which affect the decision process, and if they are received by different nodes (p and p') the nodes will decide on different values. This means that these "important messages" must be received by a single node p only.

Case 2 tests this further with the possibility that node p, the recipient of the "important messages", fails (or "takes no steps"). If a "totally correct in spite of one fault" algorithm exists, it needs to tolerate the scenario where node p fails after configuration C0. Of course, p might just not fail, and the algorithm must be correct in both scenarios: p failing and p not failing.

Since the algorithm must decide on some value, if p is failing it has to proceed through some run called sigma and arrive at a deciding configuration A.

The problem here is that if p is actually still functional, it will accept e and e' and decide on its own. As we know from case 1, node p can decide on 0 (e arriving before e') or decide on 1 (e' arriving before e). So node p is making a decision on its own with no regard for what the rest of the nodes (through sigma) are deciding and ultimately there will be a case where the 2 set of nodes decide on different values.

As for your proof, since p takes no steps (it dies after C0), it invalidates your definition of a 0-admissible run.


How does a cache handle overwriting between 2 addresses in the same block? Consider a byte-addressable cache with block size 16 bytes, bytes 0-15 form one block.
First I write an int(let's say 7) to address 0, so now bytes 0-3 contain the int 7. Now if I try to write another int(9) to address 2, then how does the cache handle this? Also if i try to read from byte 1, what effect does that have?

The lectures I'm watching suggest treating a block as the atomic unit in a cache, because keeping track of all the unwritten and written bytes will be a resource heavy task. So how will the above situation pan out? Will every block contain only 1 instance of data, with every write beginning from byte 0? because that is the only possible solution i can think of.

Your program will work exactly as if there was no cache, and as if each single memory operation was completed before the next one is started.

Typical implementations will first make sure that the complete data for a cache line is stored in the cache. So for example writing four bytes may first read the complete 64 byte line from memory.

With a line of data in cache, accessing it can be done very quickly. If there are multiple instructions reading or writing, you can expect one to be executed completely in each cycle. If instructions access different cache lines, a powerful processor may allow simultaneous access to two different cache lines. A powerful processor may also allow simultaneous access to clearly separate parts of a cache line. 4 bytes at location 2 and 4 bytes at location 6 may not count as “clearly” separate.

If you access different cache lines, the one that is accessed by a later instruction may be available in the cache earlier, and the actual access may happen earlier.


Minimum cost circulation problem with bounded number of edges During an article I am writing, I encountered the following problem:
Let $N=(G=(V,E),W,C)$ be a network with a graph $G$, a weight function $W:E\to R$ and an integer capacity function $C:E \to N$.
Find a circulation $f$ with minimal cost $W(f)$ such that the number of edges used by the  circulation (i.e., edges $e$ s.t. $f(e)> 0$) is smaller than or equal to a parameter $r$.

Note that if $r=|E|$, the problem is simply the well-known circulation, which is solvable in  polynomial time.

I tried to search "Google Scholar" and use variations of the cycle  canceling (and other min cost flow) algorithms to solve the problem but with no successes.

After I posted the question in cstheory, I received an answer there.

  Your problem is NP-Hard and even hard to approximate via easy reductions from Steiner tree problem. Look at the following paper for more information. dl.acm.org/citation.cfm?doid=1077464.1077470.


Coinduction in mathematical analysis? Coinduction is a logical principle that is somehow dual to induction. I'm struggling to understand it.

Are there any interesting examples of coinduction in analysis?

A few examples seem like they could be promising:

the $p$-adic numbers can be represented as infinite streams in such a way that the arithmetic operations are well-behaved. Therefore coinduction seems quite promising here.
continued fractions for real numbers. Unfortunately, the arithmetic operations are not well behaved in this representation; so it's unclear if it's of any use.
Real numbers with signed digits. Coinduction here is complicated by the fact that representations of real numbers become non-unique. But the arithmetic operations are well-behaved. Seems promising.
Power series.
Continued powers or "infinite radicals".

The signed digit representation of Real Numbers seems like an efficient approach for:

Defining the arithmetic operations and proving their algebraic properties. This was done already in a Master's thesis by Michael Herrmann.
Proving Cantor's theorem on the uncountability of the real numbers.
Developing the notions of continuous and uniformly continuous functions.
Proving the Extreme Value Theorem in the form that every function on $[0,1]$ has a finite supremum.
Developing the Riemann integral.

This has the nice property of being constructive.

As demonstrated by Michael Hermann, the operations listed above can be defined using colagebraic coinduction and then reasoned about using set-theoretic coinduction.

This also suggests the possibility of proving analogues of the above in $p$-adic analysis. Here, a purely coalgebraic approach might actually work.

It's possible that vast swathes of General Topology (over separable spaces) can be developed using coinduction over $\mathbb N^\mathbb N$. Here, continuous functions would be defined by corecursion over $\mathbb N ^ \mathbb N$ and then reasoned about using set-theoretic coinduction. This appears to be the approach taken in Frank'a Waaldijk's Natural Topology (I'm not sure if it uses coinduction though).

The caveat of all the above is that I've never seen a full development of the above. But the possibility certainly exists if anyone has the time or motivation.


Sound and complete algorithms for boolean satifiability To my best knowledge, these are the sound and complete algorithms for boolean satisfiability

Variations of DPLL algorithm (e.g. CDCL, Look-ahead solvers)
Stalmarks method
Binary Decision Diagram (BDD)

I am looking for other sound and complete algorithms for boolean satisfiability?

Resolution is sound and complete. In recursive learning, you recursively evaluate the clause satisfiability requirements for identifying common assignments. Look at say page 29 and onwards in these slides.


Simple explanation of Simon's Problem I just read the Wiki article for Simon's Problem but I don't fully understand it because I don't follow the symbolic notation used to describe functions (I am not a computer scientist).

Can someone just briefly explain it in simple language, like is it just XOR'ing two binary strings and trying to isolate each string? Also, if this problem is known to take exponential time to solve, why isn't it being used as a cryptographic primitive?

I think there are really three issues buried in your question.

What's Simon's Problem?
What's a plain english description of the function involved in Simon's Problem?
Why isn't this problem a cryptographic primitive?

I can't really speak to 3 as cryptography is not my area.  I can take a crack at 1 and 2 for you though.  The distinction between 1 and 2 is, I think, important.

Simon's problem is one of discovering the parameter to a function given a black-box to that function and some basic information about the function. So, an algorithm to solve this problem takes as its input a black-box to a function and gives a output a binary string.   Our goal is to reduce the number of queries to that black box.  I think people tend to miss this point and focus on the internals of the function itself.

All we know about the function $f$ is that our black-box can compute it for us in constant, $O(1)$, time, and that if $f(x) = f(y)$, then either $x=y$ or $x \oplus y = s$.  We want to know the value of $s$.   A brute force, classical computing solution might give you a better feel for the problem.  Here it is:

Feed all $n$ bit binary strings to the black-box and save each input-output pair to a table.
If no two inputs produce the same output then it must be the case that the parameter $s$ is $n$ bit $0$.  Otherwise, two inputs will produce the same output and $s$ is the result of XOR'ing those inputs together.

In the worst case, we have to query all $2^n$ inputs leading to $O(2^n)$ query complexity.

Querying the black-box is at the heart of Simon's problem.  We need not concern ourselves with how to construct the black-box, i.e. how to compute $f$, as that is not what the problem is about.  I don't believe that Simon's problem is practically useful beyond the fact that it helps establish some complexity results about Quantum Computers.  It's main significance is that it was an inspiration for Peter Shor's factoring algorithm.


Interpretation of co-NPCompleteness? Given a Problem $A$ that has an answer $true$ if and only if both (some) conditions $1$ or $2$ are $false$.

Whether condition $2$ is $true$ can be tested with certainty in polynomial time. Thus, we can say that answer to an instance of $A$ is $false$ in polynomial time (in case if $2$ is $true$). If condition $2$ is $false$, we still need to test condition $1$.

Checking if condition $1$ is $true$ on $A$ is an NPComplete problem (if we consider all possible instances of $A$).

Can we thus conclude that the original problem with both conditions is co-NPComplete?

As far as I understand your problem statement is as following:

  Given a Problem $A$ that has an answer $true$ if and only if both (some) conditions 1 or 2 are $false$.

We have a decision problem $A(w) = \overline{B(w)} \wedge \overline{C(w)}$, where $B$ and $C$ correspond to the conditions 1 and 2 respectively.

  Whether condition 2 is $true$ can be tested with certainty in polynomial time.

$C \in P$.

  Checking if condition 1 is $true$ on $A$ is an NPComplete problem (if we consider all possible instances of $A$).

$B \in NP$ and $B$ is $NP$-hard.

(Please, correct me if I misunderstood the problem statement)

So, let's rewrite the statement using the language notation: $L_B \in NP$, $L_C \in P$, and $L_A = \overline{L}_B \cap \overline{L}_C$.

By definition $L_A \in coNP$ if $\overline{L}_A \in NP$. But $\overline{L}_A = L_B \cup L_C$ (De Morgan law). Since we are given that $L_B \in NP$ and $L_C \in P$, $L_B \cup L_C$ is in $NP$ as well. So, $L_A$ is in $coNP$.

Now, take $\overline{L_C} = \emptyset$ which is clearly is in $P$, and so is $L_C = \Sigma^*$. For any $NP$-complete language $L_B$, $L_B \cup L_C = \Sigma^*$. But $\Sigma^*$ is not $coNP$-complete.


If $A \le _m B$, then $A$ decidable $\not\Rightarrow B$ decidable I'm currently reading up a bit on Turing decidability reductions as I'll take a more in-depth course about the topic next semester. While reading up on some older course material I asked myself the following question which leaves me a bit puzzled:

Let $A, B$ be languages, and $\le_m$ be the mapping reduction for languages.

For mapping reductions a central statement is

  If $A \le _m B$, then $B$ decidable $\implies A$ decidable

I'm now wondering about is whether the implication also works the other way around:

  If $A \le _m B$, then $A$ decidable $\implies B$ decidable

I strongly suspect that this is not the case as $A \le _m B$ does not even imply the existence of a mapping function from $B$ to $A$, however I'm struggling to find a good counterexample for this.

Consider $A = \Sigma^*$ and $B \subset\Gamma^*$ undecidable. If you know any $b \in B$, the constant mapping $\Sigma^* \to \Gamma^*, w \mapsto b$ provides a counterexample.

To be a bit more specific: Let $\Gamma = \{\texttt<, \texttt>, \texttt[, \texttt] \texttt+, \texttt-\}$ be the set of symbols for Brainfuck without I/O. As BF is Turing complete, we know that the subset $B \subset \Gamma^*$ of all terminating BF programs is undecidable (via the Halting problem). It turns out that $\texttt{+} \in B$.

Thus we have $A \leq_m B$ for all languages $A \subseteq \Sigma^*$ via the mapping $f\colon \Sigma^* \to \Gamma^*$ given by $f(w) = \texttt+$.


What is the difference between turing reductions and many-one reductions? To show that a particular language $A \in C$ is $C$-complete, where $C$ is some complexity class, we might construct a reduction from some known $C$-complete language $B$ to $A$, where $B$ is $C$-complete and the complexity of the reduction is asymptotically less than the upper bound of the complexity class (I just made this up, but it seems to be the case for the reduction to be at all useful; can someone verify?). Restrictions with respect to resource usage make sense to me: Why would anyone need to reduce a problem $B$ to some other problem $A$ if the computation of the reduction is greater than or equal to the computation of $B$?

However, I am taught that such reductions (showing that something is $C$-complete) must be of the many-one kind. Assume we are only talking about decision problems. Why does it matter how the reduction is done, as long as it proves whatever we are trying to prove (i.e. $A$ is $C$-Complete)?

Below are some statements I've established from my studies. Some are incomplete (I have not proven all of them), but my intuition tells me that all of these statements ought to be true. Can someone please confirm/correct my statements below?

Show A is decidable

Construct a decider $M'$ of $A$ using a machine $M$ for decidable language $B$. This reduction does not turn instances of $A$ into instances of $B$, but it still decides $A$, so we say this is a Turing reduction from $A$ to $B$.
Give a many-one reduction from $A$ to $B$. This will show that $A$ is decidable, albeit overkill.

Show A is undecidable

For some known undecidable language $B$, Give a Turing reduction from $A$ to $B$.
For some known undecidable language $B$, Give a many-one reduction from $A$ to $B$ (is this impossible?).

Show A is recognizable

For some recongizable language $B$, give a reduction from $A$ to $B$.
Give a T.M. $M$ that accepts strings in the language of $A$; $M$ is not required to reject strings not in $A$ (it may never halt).
Show its complement $\overline{A}$ is decidable.
Show that $A$ is decidable.

Show $A$ is unrecognizable

Show that $A$ and $\overline{A}$ are both undecidable.
Are there any other ways to show a language is unrecognizable?.

Show $A$ is $C$-complete

Show $A \in C$, and for some known $C$-complete language $B$, give a reduction $B \leq_m A$.

The reduction $R$ must meet the following restriction: If the complexity class $C$ has upper bound $f(x)$ on resource $S$ for some positive quantity $x$ of abstract machines that decide languages in $C$, then $g(x)$ measures the $S$-complexity of $R$ such that $g(x) \in o(f(x))$.
I'm not entirely comfortable with this definition, because, well, $PSPACE$-complete reductions are only required to have polynomial running time. In this case, I think any polynomial-time algorithm has space-complexity asymptotically less than $PSPACE$.
This line of reasoning doesn't add up either, because it is not known that $P \subset PSPACE$ (help?).

In general, it seems anywhere a many-one reductions is used, a Turing reduction may be used, but I'm not sure if the opposite is true. This is where my question about undecidability comes in: Can a many-one reduction be used to show that a language is undecidable? If this were possible, what would it imply?

You got it backwards. Turing reductions are more general than many-one reduction. A many-one reduction is also a Turing reduction, but some Turing reductions are not many-one reductions. This is provably the case for (arbitrary) computable reductions. For example, there is a Turing reduction from the halting problem to its complement, but no such many-one reduction.

Completeness is defined with respect to many-one reductions since it allows making finer distinctions. Turing reductions, for example, don't allow us to distinguish the halting problem from its complement, or NP from coNP, but many-one reductions do.


Generating values from a probability density function If I have a probability density function, some f(x) which is >= 0 everywhere and integrates to 1, is there a method to generate random numbers using that PDF?

I know there is the box-muller transform to convert uniform random numbers to gaussian, but is there anything for the general case, or at least a more general case of PDFs?

You can integrate the PDF to a CDF F(x), then uniformly generate a random number x between 0 and 1 and choose a y such that F(y)=x as your sample. This is more or less difficult, depending on your PDF. Some PDFs have analytical solutions, others need numerical methods. For some distribution Rejection sampling works well, some distributions can be sampled from using a suitably constructed Markov chain.

See also this set of slides for more details.


What is the order of this traversal method? Please see below pseudo-code for finding the max-height of a b-tree

maxDepth()
1. If tree is empty then return 0
2. Else
     (a) Get the max depth of left subtree recursively  i.e.,
          call maxDepth( tree->left-subtree)
     (a) Get the max depth of right subtree recursively  i.e.,
          call maxDepth( tree->right-subtree)
     (c) Get the max of max depths of left and right
          subtrees and add 1 to it for the current node.
         max_depth = max(max dept of left subtree,
                             max depth of right subtree)
                             + 1
     (d) Return max_depth

My guess is that this is post-order traversal.

Because we are calculating the height of the left tree and then the right tree and in the end, we find the max(left_tree_height, right_tree_height) to figure out the max height of the root node.

This is a depth first recursive binary tree traversal.

Such a traversal may be qualifed as pre-order, in-order, or post-order
if you do some specific action on each node, before the first
recursive call, between the two recursive calls, or after the second
recursive call.

Actually, you can have several actions to perform, some in pre-order,
some in in-order, and some in post-order.

In your case, you have to collect and combine the information from the
two subtrees, and that is necessarily in post-order. But it is just
using terminology, which I see as moderately meaningful in this context.

These concept often suppose an order of the daughters of a node, but this is largely irrelevant here. You can process your subtrees in any order, left first or right first. I guess that is also why I am a bit reluctant to make this postorder distinction. The pre-order, in-order, post-order distinction assumes you are exploring depth first from left to right.

They also correspond to distinct linear notations for representing binary trees, where nodes are labeled differently from leaves: prefix, infix and postfix.


Can we generate random numbers using irrational numbers like π and e? Irrational numbers like $\pi$, $e$ and $\sqrt{2}$ have a unique and non-repeating sequence after the decimal point. If we extract the $n$-th digit from such numbers (where $n$ is the number of times the method is called) and make a number with the digits as it is, should we not get a perfect random number generator? For example, if we're using $\sqrt{2}$, $e$ and $\pi$, the first number is 123, second one is 471, the next one is 184 and so on.

For any reasonable definition of perfect, the mechanism you describe is not a perfect random number generator.

Non-repeating isn't enough. The decimal number $0.101001000100001\dots$ is non-repeating but it's a terrible generator of random digits, since the answer is "always" zero, occasionally one, and never anything else.
We don't actually know if every digit occurs equally often in the decimal expansion of $\pi$ or $\mathrm{e}$ (though we suspect they do).
In many situations, we require random numbers to be unpredictable (indeed, if you asked a random person what "random" means, they'd probably say something about unpredictability). The digits of well-known constants are totally predictable.
We usually want to generate random numbers reasonably quickly, but generating successive digits of mathematical constants tends to be quite expensive.
It is, however, true that the digits of $\pi$ and $\mathrm{e}$ look statistically random, in the sense that every possible sequence of digits seems to occur about as often as it should. So, for example, each digit does occur very close to one time in ten; each two-digit sequence very close to one in a hundred, and so on.


Delaunay Triangulation on Convex Polytopes — Uniform Sampling My goal is to uniformly sample from a convex polytope. I know that for the simpler case, where I have to uniformly sample from a simplex, I can use Bayesian Bootstrap, discussed in these posts:

Uniform sampling from a simplex

Random vectors uniformely distributed into convex n-polytope

Therefore, I'm very interested in this approach. But I don't really know how to use Delaunay Triangulation here. What I have is a linear equation Ax = b and a non-negativity constraint that $x \geq \vec{0}$, and I want to sample x uniformly. Can someone tell me how to do the Delaunay Triangulation here? Thanks in advance!

This is an active area of research. Fortunately, recently there has been a breakthrough due to Vempala and Cousins [1]. They provide a MATLAB implementation of their algorithm. If you're interested in the technical details, you can check out some slides from a recent workshop.

This algorithm only samples points approximately uniformly. Exact uniform sampling, or rather the related volume estimation problem, is known to be hard (under reasonable assumptions) in general. Your convex body isn't general, however – it's a polytope. Nevertheless, the answers to this question suggest that there is no better algorithm for this special case (they suggest employing general algorithms which are older than Cousins–Vempala).

Bypassing KLS: Gaussian Cooling and an $O^*(n^3)$ Volume Algorithm by B. Cousins and S. Vempala (2014, preprint)


What does $\tilde{O}_P(N^\alpha)$ mean? What does $\tilde{O}_P(N^\alpha)$ mean? It appears in an estimation error mention in this paper, in the second paragraph on page 3.

What does big O subscript P mean in a probability context?

Pulled from: http://www2.math.uu.se/~svante/papers/sjN6.pdf (definition D5).

A probabilistic version of $\mathcal{O}$ that is frequently used is the following:
$X_n = O_\text{P}(\alpha_n)$ if for every $\epsilon > 0$ there exists constants $C_{\epsilon}$ and $n_{\epsilon}$ such that $\mathbb{P}(|X_n| \leq C_{\epsilon}\alpha_n) > 1 − \epsilon$ for every $n \geq n_{\epsilon}$. In other words, $X_n/\alpha_n$ is bounded, up to an exceptional event of arbitrarily small (but fixed) positive probability. This is also known as $X_n/\alpha_n$ being bounded in probability.

So combining this and D.W.'s answer we get:

$X_n \in \tilde{O}_{\text{P}}(\alpha_n)$ means for every $\epsilon > 0$ there exists constants $C_\epsilon$ and $n_{\epsilon}$ such that $\mathbb{P}(|X_n| \leq C_{\epsilon}\alpha_n n^{\gamma}) > 1 - \epsilon$ for every $n \geq n_{\epsilon}$ and for all $\gamma > 0$.

An looser terms $X_n \in \tilde{O}_{\text{P}}(\alpha_n)$ means $X_n$ is bounded by $\alpha_n$ within a polynomial factor with high probability.


Name for the tree formed after collapsing cycles What do you call a structure which becomes a tree after collapsing cycles (so the new vertices are the old faces)?
For instance, the digraph (given by an NFA; ignore edge labels please) below becomes a tree
$\{a,b,c,d\}$ with edges $(a,b), (b,c), (b,d)$ via:
\begin{eqnarray*}
a\mapsto&\text{the cycle }&S_0,S_1,S_2,S_3,S_4,S_5,S_6,S_7,S_0
\\
b\mapsto &\text{the cycle }&S_5,S_6,S_7,S_8,S_9,S_{10},S_{11},S_{12},S_5\\
c\mapsto &\text{the cycle }&S_8,S_9,S_8\\
d\mapsto &\text{the cycle }&S_{10},S_{11},S_{12},S_{10}
\end{eqnarray*}

For any given undirected graph $G$, the cycle graph $C(G)$ has vertices which correspond to the chordless cycles of $G$, and two distinct vertices of $C(G)$ are adjacent if and only if the corresponding chordless cycles have at least one edge in common. [1]

Judging from your example, you are interested in a similar notion for a directed graph.

[1] S.V. Gervacio. Cycle graphs. Lect. Notes Math. 1073, 279-293 (1984)


proving correctness of algorithm about graphs with DFS I need to prove/disprove the correctness of the following algorithm:
Let G be a simple, undirected and connected graph. The task is to find if the graph contains an odd cycle. The algorithm goes that way. First, you run the DFS algorithm on the graph, since it is connected it will result in a single tree. The for each node $u$, you declare the field $L[u]$. $L[u]$=0 if $u$ is the root of the tree, otherwise $L[u]=L[\pi(u)] + 1$, when $\pi(u)$ is the parent of $u$ in the tree.

Finally the algorithm says that: if there exists and edge $e=${$u,v$} in the original graph $G$ so that $L[u] + L[v]$ is even than the graph contains and odd cycle. Otherwise (if such edge doesn't exist) the graph doesn't contain an odd cycle.

I am inclined to says that the algorithm is correct. I even have an idea of a proof that uses the idea that if such edge $e$ exists, then it must be a back edge in the DFS tree. That would mean there is a cycle and since $L[v] = L[u] + t$, where $t$ is the number of tree edges in the DFS tree between $u$ and $v$, I'll get $2L[u] + t = $ even number, which means that $t$ is even and then with the edge $e$ there is an odd cycle.

However, I want to make sure that I am not missing anything, So if some one approve my way or even give an example to disprove the algorithm I would be glad.

Your algorithm is correct, but I think there's an issue with your proof. The issue is that if $u$ and $v$ are in different branches of the tree, then their distance would be $L[u]+L[v]$, not $t$.  This quantity is already defined to be even, so your proof only needs to be slightly modified to handle this case.

Edit: It is also the case that for any DFS tree, any edge not in the tree will be a back edge between nodes in the same branch. Therefore, the question asker's proof is correct.


Introduction to complexity and computability I'm looking for a good book that explains these subjects in a readable way.
Any suggestions ?

I currently pursuing my BSC in computer science, and I just failed to pass the course introduction to thr theory of computation and complexity.
I would like to have more reference and sources of knowledge so I can understand the subject better. Examples and solutions for various problems like proving undecidability, many to one reductions, etc can help me alot.

For an introduction to the theory of computation I recommend you these great books (in order of increasing "complexity"):

1) Introduction to the Theory of Computation by Michael Sipser

It is very readable, theorems are very well explained and there are plenty of exercises (some with solutions and/or hints) and references.

2) Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences) by Michael R. Garey

The "bible" of NP-completeness. Although the second part is a mere list of NP-complete problems (with hints on the reductions), the first part is a good introduction to computational complexity and is focused on the theory of NP-completeness (but there are no exercises).

3) Computational Complexity: A Modern Approach by Sanjeev Arora

... This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory, including interactive proofs, PCP, derandomization, and quantum computation....  It has plenty of examples/exercises (unfortunately some nice (advanced) topics like Kolmogorov complexity or Descriptive complexity are missing).

Finally, if you need more intermediate/advanced books on computational complexity, then take a look to Lance Fortnow's Favorite Computational Complexity books list on Amazon ...
without any doubt a bunch of "gems" :-)


Context-Free Grammar from this language I'm having difficulties with an exercise in a theoretical CS class.
The problem is:

let $L_{2}$ be a language defined as follows: after every "a" come atleast two "b" or after every "b" comes atleast one "a".

What is the CFG that creates $L_{2}$?

I'm struggling since 2h... I've found out that for example "abba" is not in the language, but to write it formally is quite difficult. Help would be much appreciated.

As Aspass.Jack wrote in the comments, let's first define $L_3$ to be the language where each $a$ is followed by at least 2 $b$'s, and $L_4$ to be the language where each $b$ is followed by at least one $a$.

Now, if let's say you can define CFGs for $L_3$ and $L_4$ with start symbols $S_3$ and $S_4$. Then, we simply need to define a grammer with the transition:
$$S \rightarrow S_3|S_4$$
together with all the transitions from the other 2 CFGs. Hopefully this simplifies your problem.


Are vector clocks useful in centralized systems? Vectors clocks seem to be a common way to synchronize the partial ordering of events in a distributed, peer-to-peer, system across all clients.

Is there any benefit to using them in a centralized system, where one node in the system has the power to order all events anyway, to order events? If one computer can decide the order anyway, there would be no need for vector clocks, right?

No, there's no need for a vector clock in a centralized system.

A vector clock uses a $N$-vector of timestamps, where $N$ is the number of computers in the distributed system and the $i$th component of the vector block is a timestamp chosen by the $i$th computer.  In a centralized system you'd use a $N$-vector with $N=1$, so it just reduces to a single number instead of a vector.  In other words, instead of a vector, all you need is a single timestamp, where the timestamp is chosen by the central computer.


Does $\#W$[1]-hardness imply approximation hardness? Let $\Pi$ be a parametrized counting problem, where the parameter is the solution cost, e.g. counting the number of $k$-sized vertex cover in a graph, parametrized by $k$.

Assume that $\Pi$ is $\#W$[1]-complete (a known problem for example would be counting the number of simple paths of length $k$ in a graph).

Does it imply that $\Pi$ is $APX$-hard (i.e. no PTAS for the problem exists unless $P=NP$)?

Note that when discussing a parameter which is the cost of solution it makes sense to discuss the approximation hardness (e.g. see this question), as opposed to other popular parametrizations.

$\mathrm{W}[1]$-hardness implies that a problem has no eptas unless (at least) $\mathrm{W}[1] = \mathrm{FPT}$ (having an eptas implies parameterized tractability for the standard solution size parameterization), but there are problems with a ptas that are $\mathrm{W}[1]$-hard (i.e. not $\mathrm{APX}$-hard unless $\mathrm{APX} = \mathrm{PTAS}$).

Transferring this to $\#\mathrm{W}[1]$-hardness, you can at least say that a $\#\mathrm{W}[1]$-hard problem still has no eptas, but I don't think a stronger statement can be made a priori. Turning to speculation, I suspect it's also not true that $\mathrm{APX}$-hardness immediately follows from $\#\mathrm{W}[1]$-hardness in general, though perhaps something may be said for higher classes, such as the counting version of $\mathrm{para}\text{-}\mathrm{NP}$.