Modal Logic - □ distribution over → In the modal logic K does □ distribution over →?

For example, would the following be correct?

□(p → q) ≡ □p → □q

No.

In the modal logic K, the formula □(p → q) implies □p → □q (by the distribution axiom) but it is not equivalent to it.

A possible intuition is as follows. Read □(p → q) as: every time it rains, my umbrella is open. Read □p → □q as: if it rains everyday, my umbrella is open everyday. In those worlds in which it rains sometimes but not always, the first formula implies that my umbrella is open on those days, the latter does not since its premise requires rain on all days.


Iterating over a solid circle of pixels Given a 2d array of pixel values, is it possible to iterate over just the pixels in a circle in a way that is less costly than simply iterating over a square and checking if a value is within the circle?

I need to get the values of pixels within a circle given center coordinates and the radius. Ideally I would ONLY iterate over the pixels in the circle as the leave number of iterations possible is the least costly for time.

The only solution I have found so far is to iterate over a square(shown in green below) and for each pixel, check if its inside the circle using pythagoras before performing the logic I wish to do.

Is there a way to only iterate over the solid circle of pixels alone?

(Int the image below, the desired pixels are highlighted in RED and the containing square is in GREEN)

thank you in advance for any help and resources offered

The most important optimization is to save resources, not only avoid traversing the full square. For this reason the best option is to calculate the upper quarter of circle (hull) and then use scanlines - traverse row for fixed number of steps. Exploiting symmetry by calculating octant algorithm may not be the best option due to random access in the array and subtraction used (it should make no difference, but it happens). This is know as the midpoint circle algorithm.

Standard way is to calculate 1/8 of the circle, reflect it and use the hull, dividing circle into rows. The naive algorithm to calculate starting points uses round operation, which is time consuming (but still worth something due to actual avoiding square traversal). More optimized version is due to Bresenham circle which avoids rounding operation.


Minimizing series of XORs Suppose you receive a list of $n$ instructions on $k$ boolean variables where each instruction has the form
$$x_i \leftarrow x_i \oplus x_j,$$
(where $\oplus$ is the binary XOR) can we efficiently find a minimal series of instructions (of the same form) that computes the same result, using up to $m$ initially zero extra temporaries?

I don't know what sort of efficiency you are looking for, it would be good if you clarified it.
Each instruction can be described as a linear map in $\mathbb{F}_2$, so the overall
series of instructions is one linear map.
As for finding the minimal set of instructions, given a limited number of temporary variables, I believe this is analogous to the register allocation problem for compilers, which is NP-COMPLETE.


what are the conditions for two NFAs to be equivalent? It's a pretty basic question, but I couldn't find an explicit answer in the book which I'm using, also when searching for it - I didn't find a reliable reference.

Correct me if I'm wrong but for two DFA's, $A , A'$ -given that  $L(A) = L(A')$ doesn't mean that the DFA's are equivalent, so what are the (sufficient and necessary) conditions under which $A$ and $A'$ are equivalent? The closest I found was a claim states that in case $\bigcup_{q\in Q} L(q) \neq \bigcup_{q'\in Q'}L(q')$ (when $L(q) = \{w\in\Sigma^* : \hat{\delta}(q_0,w) =q \})$ then $A, A'$ are not equivalent.

As commented, they are equal when they accept the same language.

In practice:

Every NFA has one (1) minimized DFA, which is unique. If two minimized DFA are equal, the corresponding NFA's must also be equal.


Maximum number of multiples of an array element preceding it Given an array of size $n$, we have to find the maximum number of multiples of $A[i]$ in the array, where the indexes of the multiples should be less than $i$.

For example, given the array

  36 40 16 24 27 12 9 4

We see that element 4 has the highest number of multiples (5) as per the given conditions, so the answer is 5.

My approach: I used brute force to solve this. I used nested loops to solve this. The first loop from the last element and the second loop from the first element to the second to last element.

Can you help me improve the running time?

Hint: note that if there are duplicates, we are basically only interested in the last occurrence of each value. Now if you maintain an array $C$ of size $\max_i A[i]$ such that at the $i$-th iteration of your algorithm $C_k=|\{j\le i, A_j=k\}|$, how can you compute the number of multiples of $A[i]$ to the left of $i$ so that the overall complexity is not too high?


Efficient data structure for matching 3D lines I'd like to

Store a set of many infinite undirected 3D lines.
Make lookups against this set - i.e. given an arbitrary line, ask "Does the set contain a line coincident with this one?"

The incidence-checks would of course have to be fuzzy to account for floating-point errors.

Question:

What would be a good data structure to implement such a set?

My thoughts so far:

Each line is originally represented as:

$$\begin{align*}
    p &= \text{an arbitrary point on the line} &= 3 \;\text{floats} \\
    v &= \text{an arbitrary vector parallel to the line} &= 3 \;\text{floats}
\end{align*}$$

To facilitate lookups, this should probably be converted such that coincident lines turn into the same tuple of floating-point numbers (within the margin of error). For example like this:

$$\begin{align*}
    p' &= \text{the point on the line closest to}\;(0,0,0) &= 3 \;\text{floats} \\
    v' &= \text{normalized direction vector} &= 2 \;\text{floats}
\end{align*}$$

Where "normalized" means unified (that's easy) and reversed in half the cases (this will be a bit tricky to do without introducing inconsistencies).

And then I'd just need a data structure for fuzzy look-up of tuples of 5 floats.

A 5-dimensional Binary Space Partitioning Tree, maybe?
Or just multiply the 5 floats together to get one float per line, use them as keys in a sorted map (e.g. std::multimap<double, Line3D*> in C++ or TreeSet<Double, List<Line3D>> in Java), and do range lookups like $[x - \epsilon, x + \epsilon)$ for a given key $x$ and error margin $\epsilon$ and then only do the full incidence check for each line in that range?

Or maybe there's an altogether different approach?

Any line can be represented in the form $\{p + xv : x \in \mathbb{R}\}$, or in other words, by a point $p$ on the line and a vector $v$ parallel to the line.  Without loss of generality, we can take $v$ to have norm 1 (if not, replace $v$ with $v/\|v\|_2$).  Also, if we ignore lines where the $z$-component of $v$ is zero, then without loss of generality we can take $p$ to be a point whose $z$-component is zero.

So, let's represent any line by the pair $p,v$, where $v$ is chosen to have norm 1 and where $p$ is chosen to have its $z$-component be zero.  Then this is a canonical representation of the line: each line has a unique representation, and two lines coincide iff their $p,v$-representations are identical.

This means that you can store each line in a hash table, where you store the pair $p,v$.  Thus, it is a hash table where each key is a 6-tuple.  You could compress it so each key is a 4-tuple (you can represent $v$ with 2 dimensions, and you only need to store the $x$- and $y$-components of $p$), but this probably doesn't gain you much.

To deal with floating-point errors, you could round $p,v$ to the nearest multiple of $\epsilon$ before storing it in the hashtable.  Or, you could store it in a data structure that supports nearest neighbor queries, such as a k-d tree.


General version of pumping lemma for regular languages, how many partitions to consider The pumping lemma for regular languages states, that one should consider a string $w = xyz, w\in L$, that is, every possible division of $w$ into $xyz$.

The article on wikipedia says, that this version is a special case of a more general version, in which one should consider strings $uwv = uxyzv$.

When using that general version of the lemma, does it require considering every possible partition of the string into $uxyzv$? I.e. does it require considering every possible $u$ and $v$?

The general version of the Pumping Lemma specifically applies to all strings $uwv \in L$ such that the length of $w$ is greater than or equal to a certain constant (the pumping length). No matter what $u$ and $v$ you pick, so long as whatever's between them is long enough, the general version will work.

So you don't need to consider all $u$ and $v$, only the ones that are useful to solving your problem. For instance, if you have the language $0^a 1^b 2^b 3^c$ where $a$, $b$, $c$ are positive integers, you can let $u$ be the string of zeroes at the beginning, let $v$ be the string of threes at the end, and then apply the simpler version of the lemma to the remaining part.

Conversely, the choice of $x$, $y$, and $z$ is harder, because the lemma doesn't guarantee that it works for all choices of these substrings, only for at least one choice of them.


Is the following Greedy algorithm to generate Gray Codes always correct? I recently solved the basic problem of generating a n-bit Gray Code. The solution I used involved building larger-bit Gray Codes from smaller ones recursively (the solution I've seen on most websites).
However, I then had an idea for a Greedy Gray Code Algorithm: Start the Gray Code at 0 and at every step, find and change the single smallest bit such that we get a new, not-visited-before number. Keep on repeating this until we have exhausted all the 2^N possible numbers with N bits.
I was sure that this approach wouldn't work for some values of N, but so far, it has worked for all N from 1 to 30. This was quite surprising for me, especially as I haven't seen this Greedy approach mentioned anywhere as a solution to the Gray Code Problem.
So, my question is, does this Greedy algorithm for generating N-bit Gray Codes always work? Is there a proof of its correctness? Otherwise, what value of N causes this algorithm to not be able to generate a correct Gray Code?

Your construction results in the standard binary-reflected Gray code, a recursive construction of which is described on Wikipedia, for example. We can also describe it in a different way: to generate the $m$'th codeword from the $(m-1)$'th, flip the least significant 1 bit of $m$. For example, when $n=3$, we have:
$$
\begin{array}{c|c}
000 & 000 \\
00\textbf{1} & 00\textbf{1} \\
0\textbf{1}1 & 0\textbf{1}0 \\
01\textbf{0} & 01\textbf{1} \\
\textbf{1}10 & \textbf{1}00 \\
11\textbf{1} & 10\textbf{1} \\
1\textbf{0}1 & 1\textbf{1}0 \\
10\textbf{0} & 11\textbf{1}
\end{array}
$$


Benefit of Backward Pass at compile time We collect most of the information about possible compiler optimizations during forward pass. Is it possible to utilize the information collected in forward pass in a backward pass so as to perform better optimizations ?

Note: I have been going through the patent Compiler with cache utilization optimizations by Roch G. Archambault et al. (2004) and was wondering what kind of information might have been utilized in their backward pass.

Many major compiler optimizations use backward passes.  For example, computing liveness information, which is used to do dead code elimination, usually requires a backwards pass over the CFG of a program in order to identify unnecessary statements.  Partial redundancy elimination, a powerful algorithm for eliminating redundant computation or rearranging code, consists of two forward passes combined with two backward passes to determine what expressions are available (forward), what expressions are anticipated (backward), etc.

Hope this helps!


What are the elements of the modular ring mod 7? Are the elements of a modular ring simply the set of all the numbers from 1 to p−1?

in this case p−1 = 6 ?

I asked this on the math stack exchange https://math.stackexchange.com/q/3375667 and was told that 0 is included in the the ring. Is this treated differently in CS ?

You might be confusing the ring and the multiplicative group of invertible elements mod p.
The first one is isomorphic to the integers from 0 to p-1, 0 being the additive neutral element, and 1 being the multiplicative neutral element.

If p is prime, the intervible elements are the integers from 1 to p-1, and they form a multiplicative group.

By the way, when p is prime, such a ring (all elements except 0 are invertible) is called a field.


Are there unary languages that are in RE but not R? Suppose that we have an alphabet Σ = {a}. My question is, is it possible to create a language with this alphabet, which is recursively enumerable, but not recursive?

My assumption is a no, i think we can construct a deterministic finite machine, which accepts every language, constructed with a single element in its alphabet.

There are undecidable unary languages.

You can consider the set of words in $\{0,1\}^*$ as essentially encoding natural numbers in binary.*  Similarly, the set of words in $\{1\}^*$ encodes natural numbers in unary. Intuitively, if a set of natural numbers is undecidable, that doesn't depend on the base in which the numbers are represented, since we can easily write algorithms to convert between bases.

Another way to see this is to observe that any decidable language (over any alphabet) is, by definition, decided by some Turing machine.  There are only countably many Turing machines, but there are uncountably many unary languages.  Therefore some (almost all!) unary languages must be undecidable.

* This isn't quite true because of the empty string and because, e.g., the strings $1$ and $01$ are clearly different but both encode the number one in binary. To get around this, say that the string $w$ encodes the number whose binary representation is $1w$.


Half precision floating point question -- smallest non-zero number There's a floating point question that popped up and I'm confused about the solution. It states that

IEEE 754-2008 introduces half precision, which is a binary
floating-point representation that uses 16 bits: 1 sign bit, 5
exponent bits (with a bias of 15) and 10 significand bits. This format
uses the same rules for special numbers that IEEE754 uses. Considering
this half-precision floating point format, answer the following
questions: ....
What is the smallest positive non-zero number it can represent?

The answer says:
bias = 15
Binary representation is: $0 \, 00000 \, 0000000001 = 2^{-14} * 2^{-10}=2^{-24}$
I've understood the binary representation part, but how does it get to those exponents of 2??

In this example, $2^{-10}$ is the mantissa, and $2^{-14}$ is the exponent.
For a fuller explanation of subnormal numbers in IEEE-754 floating point, see this previous answer.
Your example binary16 (i.e. half-precision) floating point number is a subnormal number because the exponent field is the "all zeroes" pattern. This means:

The significand field contains the fractional part of the mantissa, with an implicit "0" to the left of the binary point.
The exponent is set to $2^{-14}$. For binary32 (i.e. single precision) this would be $2^{-126}$ and for binary64 (i.e. double precision) it would be $2^{-1022}$.

So the number is $+0.0000000001_2 \times 2^{-14} = 2^{-24}$.


Can all decision problems reduce to undecidable? If one could build a machine that for any input will never accept, but always loop forever, then will all problems reduce to this?

Or did I just misunderstood the idea of reduction?

a machine that for any input will never accept, but always loop forever

isn't a decision problem, and so it doesn't make sense to say it's undecidable.

However, given an undecidable problem $A$, there are always "more undecidable" problems $B$, i.e. those which would be undecidable even given an oracle for $A$. For example, the halting problem for Turing machines extended with an oracle for $A$.


Uncapacitated facility location problem using local search I'm studying about UFLP using the book The Design of Approximation Algorithms Ch 9 starting page 233 (there is an electronic free edition), I ran into some unclear steps in the book and need some help with it.
In few words the UFLF deals with finding a subset of facilities from a given set of potential facility locations to meet the demands of all the customers such that the sum of the opening cost for each of the opened facilities and the service cost (or connection cost) is minimized
We can do the following local steps on current solution:

We can open one additional facility an “add” move.
We can close one facility that is currently open a “delete” move.
We can do both of these simultaneously a “swap” move.

Let's assume we have optimal solution and let $S^*$ be its open  facilities, and let $\sigma^*$ denote the corresponding optimal assignment of clients to open facilities. To compare the cost of this optimal solution to the current, locally optimal solution of the algorithm, we let $F$ and $F^*$ denote, respectively, the total facility cost of the current solution and the optimal one, and similarly let $C$ and $C^*$ denote their respective total assignment costs. The optimal value OPT is clearly $F^*+C^*$. Note that now $F$ stands for both the set of facilities and the cafility cost of the current solution, but the meaning at any given point should be clear from the context.

What I need help with:

Lemma 9.1: Let $S$ and $\sigma$ be a locally optimal solution. Then $$ C \leq F^* + C^* = \mathrm{OPT}. $$

Proof from the book page 235:

Consider some facility $i^* \in S^* - S$, and suppose that we open the additional facility $i^*$, and reassign to that facility all of the clients that were assigned to $i^*$ in the optimal solution: that is, we reassign all clients $j$ such that $\sigma^*(j) = i^*$. Since our current solution $S$ and $\sigma$ is locally optimal, we know that the additional facility cost of $i^*$ is at least as much as the improvement in cost that would result from reassigning each client optimally to its nearest open facility; hence, $f_{i^*}$ must also be more than the improvement resulting from our specific reassignments; that is, $$ f_{i^*} \geq \sigma_{j\colon \sigma^*(j) = i^*} (c_{\sigma(j)j} - c_{\sigma^*(j)j}). $$

Not clear what is "open the additional facility $i^*$".
Isn't $i^* \in S^*$ already open? Where does this facility open? in $S$? If so, why is it marked with a star? Doesn't that stand for the optimal solution?
I also need help with:
Proof from page 237:

Let $\phi(i^*)$ denote the facility in $S$ closest to $i^*$.
Lemma 9.3: Let $S$ and $\sigma$ be a locally optimal solution. Then $$F \leq F^* + 2C^*.$$
Consider a facility $i$ that is not safe (or, in other words, is unsafe), and let $R \subseteq S^*$ be the (non-empty) set of facilities $i^* \in S^*$ such that $\phi(i^*) = i$; among those facilities in $R$, let $i’$ be the one closest to $i$. We will derive one inequality for each member of $R$, based on an add move for each member of $R - \{i’\}$, plus one swap move closing the facility at $i$, while opening a facility at $i’$.
First let us derive an inequality for each add move corresponding to $i^* \in R - \{i’\}$. As in the proof of Lemma 9.3, we open a facility at $i^*$, and for each client $j$ that is assigned to $i$ in the locally optimal solution and is assigned to $i^*$ in the optimal solution, we reassign client $j$ to $i^*$. The change in cost caused by this move must also be non-negative, and we derive the inequality $$ f_{i^*} + \sum_{j\colon \sigma(j) = i \text{ & } \sigma^*(j)=i^*} (c_{\sigma^*(j)j}-c_{\sigma(j)j}) \geq 0. $$

If the function returns the nearest facility in $S$, what is the meaning of choosing $i'$? Isn't it just one facility that is the closest in $S$? I mean isn't $R$ of size 1? (line 2)
There is a typo and it's not Lemma 9.3 but Lemma 9.1 in the second paragraph, my second question here is also similar to the first question: what is $i^*$ here?
Any clarification will be happily welcome.

Not clear what is "open the additional facility $i^*$".
Isn't $i^* \in S^*$ already open? Where does this facility open? in $S$? If so, why is it marked with a star? Doesn't that stand for the optimal solution?

As the proof explicitly says, $i^* \in S^* - S$. In words, it is a facility which is open in the optimal solution but not in the locally optimal solution.
The phrase "open the additional facility $i^*$" indicates modifying the locally optimal solution $S$ by opening the additional facility $i^*$. This is clear from context, sine as you write, $i^*$ is already open in $S^*$, but is closed in $S$.
The facility $i^*$ is marked with a star since that's how the author chose to name this variable. The name of the variable isn't important. That said, $i^*$ is chosen by taking some facility which is open in $S^*$ but not in $S$. That is, it is part of the optimal solution but not of the locally optimal one. So the notation makes sense to me. It is using the convention that stars denote parts of the optimal solution.

If the function returns the nearest facility in $S$, what is the meaning of choosing $i'$? Isn't it just one facility that is the closest in $S$? I mean isn't $R$ of size 1? (line 2)

The set $R$ consists of all facilities in $S^*$ whose closest facility in $S$ is $i$. If $S = \{i\}$, then $R = S^*$, and in particular, $R$ could contain more than one facility. Out of all facilities in $R$, we choose the one closest to $i$, and denote it $i'$.

What is $i^*$ in the second paragraph?

As the proof explicitly says, $i^*$ is an arbitrary element of $R$ different from $i'$.


Reduction from ATM to ATM-complement Is there a reduction from ATM to ATM-complement?

(ATM denotes the language $\{\langle M,w \rangle \mid \text{TM $M$ accepts $w$}\}$)

I have been thinking about it too much and couldn't find the answer.

I know that reduction from ATM-complement to ATM is not possible becouse if it was, ATM would not be in RE. But how can I proove/profe the other way around?

By the very same reason you have mentioned there cannot be such a (many-one) reduction.

Note that if you have two problems, say $A$ and $B$, and $A\le_m B$ then also $\bar A \le_m \bar B$. In fact the same reduction can be used for both statements. So a reduction from ATM to ATM-complement, would also be a reduction from ATM-complement to ATM. And you already know that such a thing does not exist.

If you are however ask for Turing reduction, then the answer is yes. We can ask an ATM oracle and invert the answer to get a Turing machine that decides ATM-complement.


How to prove that "Total" is not recursive (decidable) $\mathrm{Halt} = \{ (f,x) | f(x)\downarrow \}$ is r.e. (semi-decidable) but undecidable.

$\mathrm{Total} = \{ f | \forall x f(x)\downarrow \}$ is not r.e. (not even semi-decidable).

I need some help in proving that $\mathrm{Total}$ is not recursive (decidable).

I know the diagonalization proof for the halting problem, I just need the same kind of proof for $\mathrm{Total}$. I'm posting the proof for the halting problem for reference:

Undecidability of the halting problem

Assume we can decide the halting problem. Then there exists some total function $\mathrm{Halt}$ such
that
$$
\mathrm{Halt}(x,y) = \begin{cases} 1 & \text{if $\phi_x(y)$ is defined}, \\ 0 & \text{if $\phi_x(y)$ is not defined}.\end{cases}
$$

Here, we have numbered all programs and $\phi_x$ refers to the $x$'th program in this ordering. We can view $\mathrm{Halt}$ as a mapping from $\mathbb{N}$ into $\mathbb{N}$ by treating its input as a single number representing the pairing of two numbers via the one-one onto function
$$ \mathrm{pair}(x,y) = \langle x,y \rangle = 2^x (2y + 1) – 1 , $$
with inverses
$$
\begin{align*}
 \langle z \rangle_1 &= \exp(z+1,1), \\
 \langle z \rangle_2 &= ((( z + 1 ) // 2^{\langle z \rangle_1}) – 1 ) // 2
\end{align*}
$$
Now if $\mathrm{Halt}$ exists, then so does $\mathrm{Disagree}$, where
$$
\mathrm{Disagree}(x) = \begin{cases} 0 & \text{if $\mathrm{Halt}(x,x)=0$, i.e., if $\phi_x(x)$ is not defined}, \\ \operatorname*{\mu}_y (y=y+1) & \text{if $\mathrm{Halt}(x,x)=1$, i.e., if $\phi_x(x)$ is defined}. \end{cases}
$$

Since $\mathrm{Disagree}$ is a program from $\mathbb{N}$ into $\mathbb{N}$, $\mathrm{Disagree}$ can be reasoned about by $\mathrm{Halt}$. Let $d$
be such that $\mathrm{Disagree} = \phi_d$, then

$$\mathrm{Disagree}(d)\text{ is defined} \Leftrightarrow \mathrm{Halt}(d,d) = 0 \Leftrightarrow Φ_d(d)\text{ is undefined} ⇔ \mathrm{Disagree}(d)\text{ is undefined}.$$

But this means that $\mathrm{Disagree}$ contradicts its own existence. Since every step we took was constructive, except for the original assumption, we must presume that the original assumption was in error. Thus, the halting problem is not decidable.

A set $A$ is recursive iff $A$ is recursive enumerable and $A^c$ is recursive enumerable. You know that $Halt$ is recursive enumerable but not recursive so $Halt^c$ must not be recursive enumerable. You can show that $Total$ is not recursive enumerable (and therefore not recursive) by showing that it is reducible from $Halt^c$.

Formally, to show that $Halt^c \leq_M Total$ you need to find a total computable function $f$ such that $$x \in Halt^c \Leftrightarrow f(x) \in Total$$


Can an alphabet be $\{ε\}$ or $\mathbb{N}$? Hopcroft says it is a finite nonempty set of symbols.

$\varepsilon$ (empty string) is not an ordinary symbol.
$\mathbb{N}$ is not finite.
So, no to both?

On the other hand, I do not see why $\{\varepsilon\}$ cannot be an alphabet. Its Kleene closure is $\{\varepsilon\}$, so a language over this alphabet can be either $\{\varepsilon\}$ or $\emptyset$, both of which are valid languages.

For the alphabet $\mathbb{N}$, I have seen on Wikipedia that an alphabet can contain an infinite number of symbols, so which claim is true? Hopcroft or Wikipedia? Personally, I do not see why that would not work.

An alphabet can be any finite set of symbols. $\{\epsilon\}$ is a finite set of symbols so you can certainly use it as an alphabet.  The strings over this alphabet are the empty string, $\epsilon$, $\epsilon\epsilon$, $\epsilon\epsilon\epsilon$, etc. Note that, in this context, we need some other notation for the empty string (some people use $\lambda$ for that anyway) and, in this context, $\epsilon$ does not denote the empty string: it denotes the one-character string whose only character is an epsilon. Likewise, $\epsilon\epsilon$ denotes the two-character string consisting of two epsilons.

Because it's confusing, we normally try to avoid having $\epsilon$ as a character in the alphabet. However, in some circumstances, it is a natural thing to do:

If you want to recognize languages of Greek words, it would be unnatural to use any alphabet other than the Greek one, $\{\alpha, \beta, \dots, \omega\}$ and that includes $\epsilon$.
If you want to write out a grammar for the strings that constitute valid regular expressions, e.g., over alphabet $\{0,1\}$, then you're going to need to use symbols $\{0,1,(,),+, {}^*, \epsilon,\emptyset\}$ (and life could get very confusing indeed).

So, if you want to stay sane, avoid having symbols such as $\epsilon$ in your alphabet as far as possible. But, if you can't avoid it, you just have to do it and use some other notation for the empty string.

$\mathbb{N}$ is not finite so it's normally not allowed as an alphabet, especially in the sort of formal language theory that's taught to undergraduates. It certainly makes sense to consider infinite alphabets in other contexts but, for most purposes, we stick to finite alphabets.


SAT Solving + Turing Machines I have a couple of questions based on how SAT solvers work. I understand that SAT solvers may employ any/all of the following techniques:

Randomness
Heuristics
Backtracking

SAT is just one example of an NP-complete problem. Is it common to use such techniques in conjunction to solve intractable problems? I normally see approaches to solving difficult problems in sections, like probabilistic algorithms or parallelism, but what stops them from being employed simultaneously?

Further to this, how is randomness achieved on a Turing machine? I mean by this pseudo-randomness, so is this possible on a Turing machine?

This is a slightly more specific question, but heuristic algorithms will have different meanings based on the problem. So if someone were to make a polynomial-time solver for another NP-complete problem like clique, based on heuristics, how would this also make SAT in P? Basically, certain methods of solving certain NP-complete problems will undoubtedly differ. How can this all at the end of the day reduce to the same problem? Can methods of solving an NP-complete problem be reduced to others?

Yes, it is common for a SAT solver to combine several techniques, e.g., random restarts with smart backtracking or other tricks. More generally, nothing stops you from throwing everything and anything at a problem you want to solve. (The reason a book might talk very specifically about say "probabilistic algorithms" instead of "here's how you solve problem X by using a probabilistic algorithm in combination with this trick, that heuristic and this data structure" is that it wants to keep focus on a specific algorithmic idea and its analysis).

The key point here is that a SAT solver is intended to be used in practice, and this is why it makes sense to combine several algorithmic techniques, data structures, etc. to achieve practical efficiency. Still, in general, no matter what the solver does, it cannot be fast and correct on every possible instance (due to NP-completeness).

To understand why having a fast algorithm for an NP-complete problem allows you to solve other such problems, look up polynomial-time reductions, and read up on NP-completeness. Here, again, it is useful to notice that all of this is perfectly fine in theory, but in practice things might be different (it is not true that "polynomial time" necessarily means "efficient in practice").


Is a String with no parantheses considered having balanced parantheses? Say I have a language over the alphabet {x,y,(,)} . The language's rules are: any string over that alphabet with balanced parentheses.

Clearly    x(),  (xy)  , ()()xxx, ((xx)) are accepted. BUT

My question is, is a string with no parentheses considered as having balanced parentheses? For example are:   y, xxyy, xyxyxxx  accepted?

And then also what about an empty String?

This is what formal definitions are for...

That said, it makes the most sense to allow no parentheses. Roughly speaking, a string has balanced parentheses if every left parenthesis is "matched" by a right parenthesis (of course this is far from being a formal definition). If there is no left parenthesis, then everything is OK.

Once you accept that, there is absolutely nothing wrong about the empty string – it is a string like any other. In particular, it is a string over your alphabet with balanced parentheses.

One way to formally define your language is using a context-free grammar. While there are many possible grammars, here is one that tried to capture the "matching" aspect when scanning the string from left to right:

$$
\begin{align*}
&S \to \epsilon \\
&S \to xS \\
&S \to yS \\
&S \to (S)S
\end{align*}
$$


Design an algorithm for efficiently computing the k smallest numbers of the form a+b*sqrt(2) Full question: Numbers of the form $a+b\sqrt{q}$, where $a$ and $b$ are nonnegative integers, and $q$ is an integer which is not he square of another integer, have special properties, e.g. they are closed under addition and multiplication. For $q=2$, some of the first few numbers of this form are given: $0 + 0\sqrt{2}, 1 + 0\sqrt{2}, 0 + 1\sqrt{2},\ldots$

Design an algorithm for efficiently computing the $k$ smallest numbers of the form $a+b\sqrt{2}$ for nonnegative integers $a$ and $b$.

(Hint: systematically enumerate points.)

I have the solution available. The first paragraph is: "A key fact about $\sqrt{2}$ is that it is irrational, i.e., it cannot equal to $a/b$ for any integers $a,b$. This implies that if $x + y\sqrt{2} = x' + y'\sqrt{2}$, where $x$ and $y$ are integers, then $x = x'$ and $y = y'$ (since otherwise $\sqrt{2} = (x-x')/(y-y')$).

I just don't see how knowing that $\sqrt{2}$ is irrational helps to reason about the problem, especially how it's a "key fact".

One way to solve this exercise is to notice that there are at least $k$ numbers of the form $a + b \sqrt{2}$ smaller than $\lfloor \sqrt{k} \rfloor + \lfloor \sqrt{k} \rfloor \sqrt{2}$ (namely, those with $0 \leq a,b \leq \sqrt{k}$). Conversely, every such number of the form $a + b \sqrt{2}$ must have $a,b \leq (1 + \sqrt{2})\sqrt{k}$. Therefore we could simply take all $O(k)$ values of the form $a+b\sqrt{2}$ with $a,b \leq (1+\sqrt{2})\sqrt{k}$, find the $k$th smallest in time $O(k)$, and then go over the list in $O(k)$ and output the $k$ smallest elements. The entire algorithm runs in time $O(k)$ (ignoring the cost of arithmetic operations).

This algorithm needs to compare two numbers of the form $a + b\sqrt{2}$. This can be done as follows. Suppose we want to determine whether $a + b \sqrt{2} \leq c + d \sqrt{2}$. If $a = c$ then this happens iff $b \leq d$, and similarly if $b = d$ then this happens iff $a \leq c$. Suppose, without loss of generality, that $d > b$. If also $c > a$ then $a + b \sqrt{2} < c + d \sqrt{2}$, so suppose that $a > c$. Then
$$
a + b \sqrt{2} \leq c + d \sqrt{2} \Leftrightarrow
a-c \leq (d-b) \sqrt{2} \Leftrightarrow
\frac{a-c}{d-b} \leq \sqrt{2} \Leftrightarrow \\
\left(\frac{a-c}{d-b}\right)^2 \leq 2 \Leftrightarrow
(a-c)^2 \leq 2(d-b)^2.
$$

What would happen to this approach if we replaced $\sqrt{2}$ by, say, 2? Then there are only $O(\sqrt{k})$ numbers smaller than $\lfloor \sqrt{k} \rfloor + 2\lfloor \sqrt{k} \rfloor$, since not all combinations of the form $a + 2b$ for $0 \leq a,b \leq \sqrt{k}$ are distinct. Indeed, we need to take the upper bound on $a,b$ to be linear in $k$ in order to find the $k$ smallest values of the form $a + 2b$. So the irrationality of $\sqrt{2}$ does make a big difference for the algorithm.


Partition points in a plane with a straigth line Given are a 2D plane and a array of points in this plane, with every point having an integer value assigned.

Is there an algorithm which, when given a ratio a/b, divides the plane with a straight line, so that the values of the points are distributed as close as possible to the given ratio?

Points may be on the dividing line, then the are counted to the 'left/upper' partition.

There is a brute $O(n^3)$ algorithm.

There are $\binom n 2 = \frac {n(n-1)} 2$ lines over pairs of points. If a line goes over $k$ points, there are $2(k+1)$ ways to rotate the line by a negligible angle, so that no points go over it and each rotation partitions the $k$ points differently.

For each pair of vertices (v1, v2),
  rotate the space so that v1.y = v2.y = 0
  let UP be the sum of values of vertices with positive y
  let DOWN be the same for negative y
  let L be a list of vertices with y = 0, sorted by x

  For each of L.length+1 ways to cut L in two,
    let LEFT be the sum of values of vertices in L to the left of the cut
    let RIGHT be the same for vertices to the right

    check whether one of UP + LEFT, DOWN + RIGHT or UP + RIGHT, DOWN + LEFT
     is a better partition than your previous best.


If A is decidable and B is decidable, then A is Turing Reducible to B The statement seems intuitively true but is it? If so, how can I prove this?

One way of defining a Turing reduction (from $A$ to $B$) is as an algorithm that can decide $A$ if we have an oracle to decide $B$. The trick to notice here is that there is nothing that says you have to actually use the oracle.

So given that $A$ is decidable, we can take the Turing machine that decides it, augment it with an oracle for $B$, but completely ignore the oracle and just run the TM as normal.


Can A still be a key if two tuples are the same I am studying database functional dependency. It says if A can functionally determine all other attributes, it is considered to be a key.

What if 2 tuples are exactly the same, can we still say A is a key? To me A cannot determine an unique tuple.

Pragmatically, You are correct that when you declare something as a primary key, that it must correspond to one tuple.  Databases will not allow you to store a tuple in a table if the primary key already exists for a tuple in the table.

Theoretically, If $R$ is a relation with the following set A of attributes $\{a_1, a_2,..., a_n\}$, then a primary key on the relation $R$ would be a subset $P \subset A$ such that for $F:P \rightarrow A$, we have $\forall x,y \in P $ $F(x)=F(y) \rightarrow x=y$.  This basically just means that the primary key forms a one-to-one mapping from the domain of keys to the range of corresponding tuples.

If you have that two tuples are the same $A$ and $B$, then this implies that $A = B$,and we still have that $F(A)=F(B)$ so that there is no violation, in that sense.


Using Data Compression on the output of Data Compression Context:

Lossless Data compression (source coding) algorithms heavily rely on repetitive  pattern (redundancy)

Questions

Is there a data compression method/algorithm that uses another data compression on the compressed data obtained so far?
 If such a method exists, what are its limits?

When we compress something the output is smaller than input (that is the purpose of compression, otherwise we do not use it or cope with bigger file). This can be achieved by various methods including (but not limited to) matching of substrings (dictionary compression) or frequency of characters (entropy compression, like Huffman encoding) or arithmetic coding (like MTF, Elias etc.).
Some methods like (Bijective) Burrows Wheeler Transform does not compress, just change the order of characters so other methods might benefit from local similarity of characters, so it is used in conjunction with other techniques.

If we try to apply dictionary method or entropy method twice (or more times) there are no benefits at all, we already exploited the redundancy of data. Using methods with chunks of data twice will give us the issue of compressing the packed data and the header (dictionary, frame, characters etc.), so it is harder task than one we started with and the most benefitial would be changing frame size or make it addaptive (but not applying the same method more times).

Encryption is not concerned about file size - it secures data with key so that any person obtaining the file without the key will have very hard time opening it. If the quality of encryption is useable the resulting file has no obvious dependencies or visible redundancy. Encrypted files are not compressible. Now encrypting chunks several times will not add any security and will not compress file.

Please keep in mind that methods like Cezar, Rot13 and xor of key (cyclic) with data are not encryption methods, and even if they were, cyclic shift of characters (mod 256) will not change compression.

About limits - when we compress something then we have to encode header, dictionary etc., so our output file is transformed input plus additional information about it, which is commonly short and not compressible, so every time we put output of compression into input of another one we have a bit more to deal with and some redundancies were already used, this is one limit.
The second limit is that we cannot compress anything in the mean sense, taking all possible inputs of given size, compressing and calculating the mean shows that we in fact ended with more data than we started with. At the best (unlikely) case we end up with the same amount of data. This comes from the fact that contraction of data with better result is not unique anymore so we cannot decompress it uniquely to original.


How does "Greedy Stays Ahead" Prove an Optimal Greedy Algorithm? I have found many proofs online about proving that a greedy algorithm is optimal, specifically within the context of the interval scheduling problem.

On the second page of Cornell's Greedy Stays Ahead handout, I don't understand a few things:

All of the proofs make the base case seem so trivial (when r=1). I don't understand the context behind the base case - perhaps in more easy to understand terms.
Are we essentially proving that the number of maximum activities in A cannot exceed the number of activities in O?

In short, are we saying that if A is not optimal, then there would be at least 1 more activity in the optimal solution, O, which would contradict our assumption that O is optimal and that A is the set of requests made by the greedy algorithm?  Because we don't say that A is optimal.  But we know that it's the set of requests selected by the greedy algorithm.  So, if it doesn't include the same number of requests than O, then we know that it couldn't have been selected by the greedy algorithm?

What we are saying is that if A is not optimal, then the number of jobs in A (let it be k) should be less than the number of jobs in O ( let it be m).

That means, there must be (k+1)-th job in O, while the k-th job is the last job in A.

Since (k+1)-th job in O must start after k-th job in O, and we know that any i-th job in A finishes earlier than i-th job in O, that means k-th job in A finishes earler than k-th job in O.

That means, the (k+1)-th job in O can be added to A, which contradicts that A only has k jobs. Hence, A must be optimal and it must have m items.


Given Directed Graph G(V,E) with red/black vertices, v is good if there's a path from v to a black vertex Given Directed Graph G(V,E) with red/black vertices, v is "good" if there's a path from v to a black vertex. in linear time.

Question: Find all the good vertices in the graph

I've come up with an algorithm which almost works.

Run SCC on G.
Sort topologically.
Run from the last SCC till the first SCC.
If we find a black node, return all the previous SCCs nodes and the current SCC's nodes (because all the nodes are reachable in the SCC).

This algorithm fails because there may be SCC's which are not connected to the SCC that we found the black node. How can I fix the algorithm to work?

Lets consider the case where you need to be $O(V+E)$. As someone in the comments mentioned, the way I thought about it was reversing the edges, as described below:

Reverse all edges
For every unvisited black vertex, perform a BFS/DFS on all unvisited nodes, marking them visited as you search.
All visited nodes are good.

It is trivial to see that if and only if a node is marked visited, it can reach a black vertex in the original graph. The forward direction is simple, if a node is visited, then there is a direct path to a black vertex. The other direction is also true, if there is a path from a node to a black vertex in the original graph, that that node would clearly have been visited by one of the searches.

Now, let's say you want to stick with the SCC strategy. We first find all SCC's in $O(V+E)$ time. Then, for each SCC we condense it to a single node and color it black if it contained a black node and red otherwise. All edges into and out of the each SCC will now lead into and out of the new corresponding condensed node. Now we can just perform the same algorithm as above on the new graph with no SCCs! For every node, mark it as good iff its corresponding SCC was visited.


Finding an algorithm that minimizes vertex weight sum of a subgraph that satisfies several constraints I have a vertex-weighted undirected graph $(V,E)$ with root vertices $R = {r1, ..., rn}$. I need to find the subset $V'⊂V$ such that $R⊂V'$, $N[V']=V$, $∀v'∈V '[∃r∈R ($path($r', v'$)$)]$ that minimizes the sum of vertex weights in $V'$. Note the path must contain only vertices in $V'$.
In other words, all roots must be in $V'$, the closed neighborhood of $V'$ must include all vertices in the original graph and every vertex in $V'$ needs to have a path to a root.
I have constructed a naive algorithm that takes the powerset of $V$ and checks for each subset if it satisfies the 3 constraints. The first constraint is trivial, the second requires the algorithm to compare the union of $V'$ with $V$, and the third one is done by using DFS (only adding vertices to discovered if they are in $V'$.
I was thinking I could convert the vertex-weighted undirected graph to a edge-weighted directed graph and then run Chu-liu/Edmonds' algorithm to find a minimal spanning arborescence. I tried converting the graph by adding $v'$ for each $v$ in $V$, with an edge $(v,v')$ with the vertex weight. All outgoing vertices from $v$ will now be outgoing from $v'$. The problem is that these auxiliary vertices don't need to be included in the MSA, but Chu-liu/Edmonds' algorithm will include them.
Actual question: Is there a better way to convert the graph, so that I can use this approach, or should I go for another (maybe even easier) approach?

Without loss of generality we can assume the graph is connected.  (If not, decompose it into connected components, and solve the problem separately on each component.)  Since it is connected, every vertex has a path to every other, so we can ignore the requirement to have a path to a root.
So your problem becomes: given $R$, find a minimum dominating set $V'$ that contains $R$.  This is NP-complete; indeed, the special case where $R=\emptyset$ is the standard dominating set problem, which is NP-complete, so your problem is, too.
If you need to solve your problem in practice, you could apply any of the standard techniques for dominating set or set cover.  For instance, you could use an approximation algorithm or greedy heuristic to get an approximate solution; or you could use a SAT solver or ILP solver to get an exact solution and hope that it terminates in a reasonable amount of time on your specific problem instances.


Match students and teachers based on ranking I have a similar question to that of Stable Marriage Problem.

This is the criteria1) 1 Student must have 1 Teacher only.2) 1 Teacher ideally should have 3-4 Students.

The spreadsheet is done using Google Apps Script (Javascript).
How do I go about with the system calculation and giving teachers the system-generated result (3-4 Students) ?

Your problem differs from stable marriage problem in a minor way. A teacher can have 4 students maximum. You will have to fix the maximum students allotted to teacher (you may not have 3-4, if you also prescribe minimum number of students then you might have to dig deeper).

Now you can do two things, first, have four copies of each teacher and solve the stable marriage problem. Second solution is essentially like first but you keep a list of 4 "engagements"  for each teacher.


Proving that a set of grammars for a given finite language is decidable Let the language $$L = \left\{ \langle G \rangle \ |\ L(G) = \{1,\ldots , 1000\}, \text{ G is a CFG }\right\}$$

  Prove that $L \in R$.

Well, I think that for a start we need to check whether or not $L(G)$ is infinite, so we only need to check if there's a word $w\in L(G)$ such that $n \le \left|w\right|\le 2n$

Suppose $L(G)$ is finite. How can I validate that $L(G) = \{1,\ldots ,1000\}$?

Hint: Combine the following two properties of context-free grammars:

Given a context-free grammar $G$ and a regular language $L$ (given by a DFA, say), there is an algorithm that constructs a context-free grammar $G'$ satisfying $L(G') = L(G) \cap L$.
Given a context-free grammar $G$, there is an algorithm deciding whether $L(G) = \emptyset$.


Are there any implementations of the spineless tagless G-machine other than in GHC? From Simon Peyton Jones (recent Royal Society member) we read the paper: Implementing lazy functional languages on stock hardware: the Spineless Tagless G-Machine.

Now this paper is part of how they made Haskell a lazy language when they were implementing it, and solved some problems they had at the time.

The only comparable paper seems to be: Compiling Lazy Functional Programs Based on the Spineless Tagless G-machine for the Java Virtual Machine but there doesn't appear to be an implementation available.

One tangentially related is: Compiling Haskell to Java. However in this approach they leave the implementation of the Spineless Tagless G-Machine in GHC and just read the output.

My question is: Are there any implementations of the spineless tagless G-machine other than in GHC?

I used this Google search:

"spineless tagless g-machine" site:github.com

and found 2 repos that (try?) to implement the STG in non-Haskell languages:

PHP: lechimp-p/php-stg

RPython ("restricted" subset of Python developed for Pypy): cgswords/laurens


PSpace-completeness under PSpace reductions A language $L$ is PSpace-complete, if it meets two conditions:

It is in PSpace.
Every other PSpace-complete language reduces to it in polynomial time.

Question: suppose we change the second condition to polynomial space (instead of time)?
Why is it so that then SAT would be PSpace-complete?

Every language $X$ in PSPACE would be complete under your proposed definition, except for $\emptyset$ and $\Sigma^*$. You could reduce any PSPACE language $Y$ to $X$ by a reduction that first decides whether its input $w$ is in $Y$ and then maps to a fixed "yes" instance of $X$ if so, and a fixed "no" instance if not.

Note also that the actual definition of PSPACE-completeness requires that every language in the whole of PSPACE reduces to the complete language. The definition you've given is circular, since it defines PSPACE-completeness in terms of itself.


Ant colony optimization for continuous functions I am trying to do optimization of a voice activity detection function, which is a function with continuous parameters. This is easily accomplished with genetic algorithms, simulated annealing, and tabu search, but I'm somewhat confused on how to accomplish this with Ant Colony Optimization (ACO).

From what I've read, ACO is mostly used for solving problems that can be formulated as a graph. I've searched for resources relating to multiple parameter function optimization, but the closest thing I found was this article for a single parameter on a continuous function and this long paper with no pseudocode which is contained in this PHD thesis. Are there any resources (websites or books) for accomplishing multiple parameter continuous function optimization with ACO that involve an implementation example?

Alternatively, is the key here to discretize the continuous inputs? If so, what methods exist to do this in a way that works well with ACO?

No, discretizing solution space is not necessary

I read page 14 of paper you provided and then went googling.

I found this 2014 paper: A unified ant colony optimization algorithm for continuous optimization that mentioned a bit of history of ACO on continuous function.

Tracing from that, I think the best paper to begin is this 2008 paper Ant colony optimization for continuous domains coauthored by the original creator of ACO, Marco Dorigo, himself.

Quote from page 76 this paper:

  The fundamental idea underlying $ACO_R$ is the shift from using a
  discrete probability distribution to using a continuous one...

That is instead of remembering pheromone value in discrete boxes, you remember in a form of probability distribution function (PDF) that is parameterized for updates. The moving of the ants (solution points) is also continuous.
The ants move random directions across the dimensions of solution space (as opposed to moving from box to box as in the first paper you gave.)

I hope I have answered some of your question and provide some references for further reading without digging too deep in myself.


Solving recurence relations $T(n) =
\begin{cases}
2: & n=0\\
5: & n=1 \\
2T(n-2) - T(n-1): &n \geq 2
\end{cases}$

I have found a few examples including https://math.stackexchange.com/questions/1316301/if-tn-tn-1-2tn-2
But I am still lost about how to solve this one.

Here's a general technique on linear recurrences that's useful to know. Observe that:

$$
\begin{bmatrix}
T(n) \\
T(n+1)
\end{bmatrix} =
\begin{bmatrix}
0 & 1 \\
2 & -1
\end{bmatrix}^{n}
\begin{bmatrix}
2 \\
5
\end{bmatrix}$$

If we can perform an eigendecomposition of $M$:

$$M = Q \Lambda Q^{-1}$$

where $\Lambda$ is a diagonal matrix, then:

$$M^n = Q \Lambda^n Q^{-1}$$

Raising a diagonal matrix to a power is trivial. This gives you a closed form for $M^n$.

In your case:

$$\begin{bmatrix}
0 & 1 \\ 2 & -1
\end{bmatrix} =
\begin{bmatrix}
-\frac{1}{\sqrt{5}} & \frac{1}{\sqrt{2}} \\
\frac{2}{\sqrt{5}} & \frac{1}{\sqrt{2}}
\end{bmatrix}
\begin{bmatrix}
-2 & 0 \\
0 & 1
\end{bmatrix}
\begin{bmatrix}
\frac{-\sqrt{5}}{3} & \frac{\sqrt{5}}{3} \\
\frac{2\sqrt{2}}{3} & \frac{\sqrt{2}}{3}
\end{bmatrix}$$

So:

$$
\begin{bmatrix}
T(n) \\
T(n+1)
\end{bmatrix} =
\begin{bmatrix}
-\frac{1}{\sqrt{5}} & \frac{1}{\sqrt{2}} \\
\frac{2}{\sqrt{5}} & \frac{1}{\sqrt{2}}
\end{bmatrix}
\begin{bmatrix}
-2 & 0 \\
0 & 1
\end{bmatrix}^n
\begin{bmatrix}
\frac{-\sqrt{5}}{3} & \frac{\sqrt{5}}{3} \\
\frac{2\sqrt{2}}{3} & \frac{\sqrt{2}}{3}
\end{bmatrix}
\begin{bmatrix}
2 \\
5
\end{bmatrix}$$

Multiplying the matrices together, taking the top row, and simplifying gives:

$$T(n) = 3 - (-2)^n$$

It's a lot of work (if you don't have a computer algebra system handy), but it always gives an answer if the system is linear and diagonalisable.


"Equivalent device" for testing for NP and coNP? I'm trying to understand some aspects of the $P=^?NP$ and $NP=^?coNP$ problems.

I am engineer and not mathematician nor computer scientist so I do not completely understand what a turing machine is.

I'm currently thinking about a variant of the "subset sum problem" known to be in $NP$ and suspected to be not in $coNP$. However I'm thinking of a modified variant of the problem.

It is easy to prove that a computer based on a "real" CPU can prove the answer "yes, a subset exists" (when the subset is known) in less than $(n+a)^2$ operations (while $a$ depends on the type of CPU used) when the original set contains $n$ elements.

From my understanding of $NP$ this implies that the problem belongs to $NP$. My first question is if this understanding is correct.

(I write "belongs to $NP$" and not "$\in NP$" because I know I mix up terms like "problem", "formal language", ...)

I suspect the minimum number of operations (on the real CPU) to prove the answer "no, no matching subset exists" to be more than $\frac{2^n}b$ (while $b$ depends on the type of CPU used).

So my second question is if this would mean that the problem does not belong to $coNP$.

As far as I know that there are differences between Turing Machines and CPU-based computers:

A Turing Machine has unlimited memory while a computer has limited memory
A Turing Machine can't generate true (undeterministic) random numbers while on a computer you may use the noise of the microphone input...
...

So I'm not sure if "cannot be calculated by a computer in polynomal time" implies "cannot be calculated by a Turing Machine in polynomal time".

-- Edit --

Having read the answers I think I have to say something about the background of the question:

I think I had already understood what P, NP or coNP is before asking the question but I was not 100% sure because I was not sure about the differences between a Turing Machine and a computer.

I have an idea how it could be possible to prove the impossibility to build a digital computer that can solve a certain problem in less than $a^nb$ steps while $n$ is the number of inputs and $a$ and $b$ depends on the computer and the problem.

I was just wondering if such a proof was sufficient to prove $P \neq NP$ if it could be done for a problem that is known to be in NP.

Having read your answers I think that such a proof would be sufficient. Thanks.

(Needless to say that I am not able to carry the proof I'm thinking of for any problem.)

I will not directly answer your questions, as this would result in explaining the definitions of $\mathsf{NP}$ and $\mathsf{coNP}$, which has been done before. However, using the following hint combined with the definition of the complexity classes indirectly answers your questions.

A modern computer with unlimited memory is equivalent to the concept of a register machine, which in turn is turing equivalent. Thus everything that can be computed on a modern computer with infinite memory can also be computed by a turing machine and vice-versa.

  A Turing Machine can't generate true (undeterministic) random numbers
  while on a computer you may use the noise of the microphone input...

A microphone, or any other hardware-based true random number generator, is an input of the computer. That means the values delivered by it are not computed by the computer itself. Note that you can also model random input by a two-tape turing machine, where one tape contains the random numbers.


How to represent/implement the hypotheses class for a DAG learner I am implementing a learner to learn a DAG model $G=\langle V,E\rangle$ where $V$ and $E$ represent both variables and dependencies respectively ( similar to Bayesian networks). Each variable $v\in V$ is associated with possible values (domain) $D_v$ and a function $\theta_v$.

I assume the learner knows the number of variables $n$ (i.e. vertices) and their possible values (domain). The goal is to find $E$ (dependencies) and $\theta_v$ for every variable $v$. I also assume there is a target function $c$ exist (the realizable case).

The hypothesis class is defined as the set of consistent hypotheses i.e. $H=\{h|\ h(x)=c(x)\} \forall x\in S$ where $S$ is set of examples seen so far.

I am trying to find a way to represent my hypotheses class. Initially, before receiving any example, it contains:

all possible DAGs over $V$.
all different combinations of $E$ as long as its acyclic.
For every Graph $G$ generated from (1) and (2),all different function values over $G$.

Beside my naive representation, I do not know how to compute (1) precisely. To put my question in another way, how to represent the hypotheses class over Bayesian networks?

OK here is what I did:

I read about the most specific $ms$ and most general $mg$ hypotheses here. Intuitively, the hypotheses class is defined as these two hypotheses and anything in between.  That is, for a hypothesis $h$ with DAG $G_h$, in order for $h$ to be in the hypotheses class $H$, it must be the case $G_{ms}\subseteq G_h \subseteq G_{mg}$.

For now, I used only $ms$ since my problem transformed to learning only one labelling $\{+\}$.  Initially $G_{ms}=\emptyset$. Every example $x$ consist of pair of vertices $(x[a],x[b])$. if $\zeta(x)=\{+\}$ then there is an edge from $x[a]$ to $x[b]$ in $G_{ms}$ where $\zeta(x)$ is the labelling of $x$ according to the target function $h^*$.

After seeing $i$ examples $G_{ms}$ has $i$ edges. Any hypothesis $h$ with $G_{ms}\subset G_h$ is included in my hypotheses class $H$.


Construct a DFA recognizing a language $L$ that has exactly $I(L)$ states Let $L$ be a language, and consider the following relation $\equiv_L$ on strings:
$s_1 \equiv_L s_2$ if and only if, for every string $w$, we have that $s_1w \in L \Leftrightarrow s_2w \in L$.
This is an equivalence relation.
Let $I(L)$ be the number of equivalence classes of $\equiv_L$
(a) Suppose $L$ is a language and $I(L)$ is finite. Construct a DFA recognizing $L$ that has
exactly $I(L)$ states.
(b) Consider the language $L = \{www : w \in \{a,b\}^*\}$. Show that $L$ is not regular by giving
infinitely many pairwise inequivalent elements. [which is something proven to work earlier]

Now, for (a) I think I got a reasonable solution, for (b) I don't feel so sure.
For part (a) I describe an algorithm which first creates a start state for the DFA and labels it $\bar\varepsilon$, i.e. the $\equiv_L$-equivalence class of $\varepsilon$. Second, for each letter $a$ in the input alphabet a new state $\bar a$ is created and a transition from $\bar\varepsilon$ to $\bar a$ is labelled $a$. Then all the states with the same label are merged in a single state, and the transitions are adjusted as a consequence. Hence, this procedure just carried on $\bar\varepsilon$ is iterated to each state just added. The algorithm stops when an iteration does not add any new state or transition.
Do you think that the writer wanted me to use this much information about $\equiv_L$-equivalence classes or there is a neater solution?
For part (b), I believe that all the words generated by $ab^*$ are pairwise not $\equiv_L$-equivalent, with that $L$. Am I not sure I can justify it further than this, but is there another simpler example?
Thank you for any help, this is a rather long question.

(a) Let $\Sigma$ be the alphabet of $L$ and $\Sigma^*/\equiv_L$ the set of equivalence classes of words over $\Sigma$ according to the equivalence relation $\equiv_L$. Define the DFA to have one state for each element of $\Sigma^*/\equiv_L$ (we could think of the states as the classes themselves). Define the initial state to be the class of the empty word $\epsilon$, the accepting states to be the classes of the words in $L$. For each pair of states $s_1,s_2\in \Sigma^*/\equiv_L$ and letter $t\in\Sigma$ we will have the value of the transition function $\delta(s_1,t)=s_2$ if and only if for a word (equivalently, for all words) $x\in s_1$ we have that the word $xt\in s_2$.
(b) The examples that you showed work. The classes of the words $ab^n$, for $n=1,2,...$ are all different. In fact, if $x=ab^m$, $y=ab^n$ and $m>n$, then taking $w=ab^nab^n$ we get that $xw\not\in L$, while $yw\in L$. Therefore, $x\not\equiv_L y$.


Difference between 1* + 0* and (1 + 0)* I know that (1 + 0)* is the set of all bit strings; but isn't  1* + 0* the same thing?

The set $1^*+0^*$ is composed of two parts: $1^*$ and $0^*$. The first part, $1^*$, is all strings composed entirely of $1$s. The second part, $0^*$, is all strings composed entirely of $0$s. In contrast, $(1+0)^*$ is all strings composed of $0$s and $1$s. Can you now think of a string in $(1+0)^*$ but not in $1^*+0^*$?


Have I got the right understanding of the mu operator? I have a homework problem that says:

For $g(x,y)=xy-5$ compute $h(x) = \mu y(g(x,y))$ and determine its domain.

I was under the impression that this means the least y such that $g(x,y)=0$, so then $y = \frac{5}{x}, D=\{x \in \mathbb{N}, x \neq 0\}$

So $h(x)=\frac{5}{x}$?

Hint: $h(x)$ is always a non-negative integer (whenever it's defined).

As a side note, usually primitive recursive functions are assumed to be non-negative, and so $\max(xy-5,0)$ is more usual than what you wrote.


Partitioning planar graphs without minimizing edge cuts I am looking for an algorithm that, given an undirected, planar graph $G = (V,E)$ with node weights, meets the following conditions:

Creates balanced (within some margin) $k$ partitions of $V$ according to node weight.
All partitions have to be connected.
It cannot minimize communication volume, or edge cuts.

My graphs are planar, all vertex weights are positive integers, and the reason that I want #3 is that I need to be able to generate $n$ distinct partitions from the graph that I have. I have found that if I use GPMetis, no matter what options and seed I pass it (currently using -seed=40 -ctype=rm -iptype=random -ptype=kway). The options have an impact only if I scale up the number of vertexes (on my graphs that have less than 100 nodes, it always gives the same answer).

Are there algorithms that exist to create balanced partitions by vertex weight that meet these conditions? It doesn't need to ignore edge counts/weight entirely, so long as I can still make the result different via some seed. Willing to take either a research paper, or fully functional code.

As background:

I know that a vertex separator can be found in polynomial time for planar graphs, but I need all my vertices.
There are several edge cut algorithms that also run in near polynomial time, but these have the problem listed above of not being able to inject sufficient randomness.

One general method is to perturb the node weights slightly, find a good partition, and repeat that $n$ times with $n$ different perturbations.

The basic algorithm is something like this:

Repeat until you have $n$ distinct balanced partitions of $G$:

Copy $G$ to $G'$.  Randomly perturb the weight of each node in $G'$ by a tiny amount (a different random change for each node).
Find a balanced partition of $G'$.  This corresponds to a partition of $G$.
If this is a legal, balanced partition of $G$ and you haven't seen this partition of $G$ before, add it to your list of distinct partitions.

If you choose the amount of the perturbation correctly, then you can expect this will need only $O(n)$ iterations of the loop to find $n$ distinct partitions.

Let's see in a little more detail how to make this work in your setting and why it works.  The basic idea is to add a tiny, tiny random perturbation to each node's weight.  This won't affect the total weight of any group in your partition by very much: the sum of a bunch of of tiny numbers is still quite small, and in particular, we can ensure it will be much smaller than 1.  Since the total weight of any group of vertices in $G$ has to be an integer, the change in its total weight can't be enough to make it jump up to the next integer.   Consequently, this won't change the relative order of vertex-groups (if one vertex-group has a smaller weight than another vertex-group, after perturbation its weight cannot become larger); all it can do is break ties.

However, this basic idea has a problem: after perturbation, the vertex weights in $G'$ are no longer integers.  It's possible that your underlying algorithm (e.g., Metis) requires the vertex weights to be integers.   If so, here is how we can fix things up and preserve the integrality of node weights.  The idea is to first scale up all of the weights by a large integer constant $c_1$, then add a small integer perturbation to each node weight.  Formally, let $w_v$ be the weight on node $v$.  We're going to pick integer constants $c_1,c_2$ and for each node $v$ set

$$w'_v = c_1 w_v + r_v,$$

where $r_v$ is a random integer chosen from $\{0,1,\dots,c_2\}$ (chosen independently for each node).  We'll use $w'_v$ as the weight of node $v$ in $G'$.

How do we choose $c_1,c_2$?  Basically, we need $c_2$ to be large enough so that each iteration is likely to give you a new partition, and we need $c_1/c_2$ large enough so that a balanced partition of $G'$ is likely to also be a balanced partition of $G$.  One reasonable setting is to use $c_2=100n$ and $c_1 = 100 |V| c_2$.  Alternatively, if your underlying algorithm is OK with non-integer vertex weights, you could instead pick $r_v$ randomly from the range $[0,1/(100|V|)]$ and just leave $c_1=1$.

Why does this work?  Well, first note if we divide all the weights in a graph by a constant, that has no effect on the set of balanced partitions -- so we might as well consider the weights to be $w''_v = w_v + r_v/c_1$.  Now I claim that a balanced partition of $G'$ is almost certainly a balanced partition of $G$.  Any single group in the partition has at most $|V|$ vertices, and the weight of each node in the group has been randomly increased by at most $c_2/c_1$, so the total increase in the weight of that group is at most $|V|c_2/c_1=0.01$.  Originally the total weight of a vertex-group has to be integer, so this perturbation is not enough to make it jump up to the next integer.  Now, depending upon your definition of balanced, most likely the following will be true: any balanced partition in $G'$ has a high probability of being a balanced partition in $G$.

Also, the random perturbations ensure that, if you look at two perturbed graphs $G'_1,G'_2$, it is unlikely that the optimum partition of $G'_1$ is the same as the optimum partition of $G'_2$.

So, I suggest you give this a try.

Important caveats: There are no guarantees this will work.  From a theoretical perspective, it's not guaranteed to work.  Indeed, I suspect your problem might be NP-hard, so it would be too much to expect this to always work.  But in practice, this often works, if you are in a situation where your underlying algorithm (e.g., Metis) is able to find the optimum partition in a reasonable amount of time.  As a pragmatic guideline, it's more likely to work if the underlying algorithm can find an exact optimum rather than an approximate-optimum (e.g., maximally balanced rather than close-to-maximally-balanced).  However, as I said, there are no guarantees, so the best way to find out whether it will work in your particular situation is to try it out and see.


Heterogenous and Asymmetric Computing's differences The definition of the both architecture looks pretty same. They are parallel computing architecture with different type of cores.

What distinguish their definition, actually?

Heterogenous computing as opossite to homogenous or symmetric means that processing units differ, which is exactly the same as asymmetric (which is just not symmetric).
But there are more usage differences - asymmetric computing (processing) is more about different CPUs which are used to perform assigned tasks, in embedded systems this is by design, in general purpose by executing in given context, commonly about "local" environment.
Heterogenous is used to talk about tasks computed on different processing units (CPU, GPU and dedicated hardware), also used to describe distributed systems where processing takes place on totally random devices connected.

To make it full - symmetric means exactly the same vector, while homogenous is less strict and requires the results to be the same among devices (the same floating point representation), but does not require exact devices.


lower bound for Renyi–Ulam Game with lies Player $A$ thinks of number between 1 and $n$ and ask $B$ to guess the number with minimum number of decision queries (yes or no type ).

Game :

$A$ chooses an element in {1,2....,n}
$B$ tries to guess this number by asking Yes/No
questions.

Binary search is a way to solve the problem, so with $\log n$ many queries will be sufficient to solve the problem when player $A$ does not lie. But if player $A$ lie exactly one time than we can problem with $2\log n$ many queries (by just asking the same query two times). There is an optimal way to solve this problem with $ \log n + \log \log n +c$ , where $c$ is a constant. We will first ask $\log n $ many queries to $B$ and going to get a $\log n $ bits long binary string and now apply binary search on this binary string. In general when A is allowed to lie say $l$ (constant) then also the number of queries need to solved the problem is $ \log n + \log\log n + c $

Questions : 1) How to prove that $ \log n + \log\log n + c$ is a lower bound ?

2) If only $\log n$ many queries are allowed in the general case Is there an approximation algorithm for this game ( original solution = $a$ * algorithm's solution, where $a$ is constant).

3) If $l$ is very large (say order of $n$) Is it possible in that case to correctly find out the guessed number ? I tried to use the  Hamming distance but not able to come up with a precise answer.

Reference :http://ac.els-cdn.com/S0304397503005814/1-s2.0-S0304397503005814-main.pdf?_tid=a880fa14-f82d-11e6-81df-00000aacb35e&acdnat=1487678746_7307f01621c154d9f6e006fc8b992ad0

For the first question, suppose that you have an algorithm that supports one error, and uses $m$ questions. For each element $i \in \{1,\ldots,n\}$, let $x_{i0}$ be the vector containing the answers to all questions when A doesn't lie, and let $x_{ij}$ be the vector containing the answers to all questions when A lies in question $j$. In total, we have $n$ collections of $m+1$ vectors. All these vectors are distinct: the $m+1$ vectors in a collection are distinct by definition, and vectors belonging to different collections must be distinct since the correct answer is different. We deduce that $(m+1)n \leq 2^m$, and so $m \geq \log n + \log\log n + \Omega(1)$.

For the second question, here is something to try. Let $m$ be a number so that $\log n$ queries suffice to find an element in $\{1,\ldots,m\}$, even when A is allowed to lie at most once. Partition $\{1,\ldots,n\}$ into $m$ intervals $[x_1,x_2),[x_2,x_3),\ldots,[x_m,x_{m+1})$, where $[a,b) = \{a,\ldots,b-1\}$, $x_1 = 1$, and $x_{m+1} = n+1$. Then this gives an $\alpha$-approximation for $\alpha = \max \frac{x_{i+1}-1}{x_i}$. I leave the rest to you.

The third question is addressed in Three thresholds for a liar by Spencer and Winkler. The threshold is $n/3$ (a strategy exists if $\ell < n/3$).


Match unpaired points between two sets I have two sets, let's call them C and T, of unpaired points, which could for example represent two types of cells. Hence, both points are drawn from the same underlying distribution, but the points in T underwent an additional process/function.
Although biologically debatable, I want to find the most similar points in the T set for each point in the C set. It does not need to be a 1:1 mapping, 1:n is also possible, because the sample sizes might be different.
How can I find such a mapping? Do you know any algorithms (or have other ideas) to achieve this?
First, I thought it makes sense to span a graph in both sets by drawing edges between points which are below a certain distance. The distance for each set has to be such that the number of vertices with n edges are approximately the same in both sets. Afterwards I could match all points with k neighbors in set C, with all points with k neighbors in set T. Although I have not implemented this yet, I am unsure how efficient this will be.

This is called the Assignment Problem, or equivalently Weighted Bipartite Matching.
You need a way to compute a numeric distance or cost between any point in C and any point in T (it sounds like you already have this). Create a graph with a vertex for each point in C, and a vertex for each point in T, and an edge between every pair of vertices from different sets (i.e., one from C, one from T) having weight equal to the cost between them, and run one of the several algorithms described on that page, e.g., the Hungarian algorithm, which can be implemented to run in $O(n^3)$ time though the description on that page is only $O(n^4)$. As this might be tricky to implement, I would suggest instead setting up a linear program and using a freely available LP solver to solve it.


Draw a function by only using two input NOR gates T = (BD + A'BC'+A'CD)

How can i draw this by only using NOR-Gates? This is what i have done so far:
https://imgur.com/a/JG2eU

Have I understood this right?

Yes, looks like you understood the question correctly and are implementing only using NOR-gates.

I also see correct usage of DeMorgan's Theorem.

Your answer seems to be correct. Good luck!


Two languages such that $L_1 \cup L_2 \leq_m\, L_1 \cap L_2$ and two (other?) such that $L_1 \cap L_2 ≤_m\, L_1 \cup L_2$? Are there languages $L_1$, $L_2$ such that such that
$$L_1 \cup L_2\leq_m\, L_1\cap L_2,$$
and two other languages such that
$$L_1 \cap L_2 \leq_m\, L_1 \cup L_2?$$
And if so, what are they? How can i go about finding these?

How about taking $L_1=L_2$? Then we will have both
$L_1 \cup L_2\leq_m\, L_1\cap L_2$ and $L_1 \cap L_2 \leq_m\, L_1 \cup L_2$.

If you want to have $L_1\not= L_2$, you just try $L_2=L_1\cup\{w\}$, where $w$ is a string not in $L_1$.

If you are determined to have infinity elements in both $L_1\setminus L_2$ and $L_2\setminus L_1$, try $L_1=L\cup aL$ and $L_2=L\cup bL$, where $L$ is an infinite language over $\Sigma$ and $a,b$ are two new symbols not in $\Sigma$.

By now, you should be able to see that there are lots of way to construct examples that satisfy the requirements.


Do we need both path compression and union by rank together in disjoint set data structure? I was studying disjoint set data structure. I studied path compression and union by rank. Initially all the elements are single in their own set and by performing unions we can combine different sets.
Now since we are performing union by rank the height of the resultant tree is always minimum. At this point i think that we might not need path compression at all. Am i right? If i am wrong please explain me with an example.

No, you are not right, at least not if you want the fastest possible running times.  Using both is faster than using just one of them alone.  Using just Union by rank gives you a $O(m \lg n)$ running time per operation, whereas using both Union by rank and path compression gives you a $O(\alpha(n))$ running time per operation, which is asymptotically faster.  Here $n$ is the number of elements and $m$ is the number of operations performed on them. See https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Time_complexity.


Data compression using prime numbers I have recently stumbled upon the following interesting article which claims to efficiently compress random data sets by always more than 50%, regardless of the type and format of the data.

Basically it uses prime numbers to uniquely construct a representation of 4-byte data chunks which are easy to decompress given that every number is a unique product of primes. In order to associate these sequences with the primes it utilizes a dictionary.

My question is:

Is this really feasible as the authors suggest it? According to the paper, their results are very efficient and always compress data to a smaller size. Won't the dictionary size be enormous?
Couldn't this be used to iteratively re-compress the compressed data using the same algorithm? It is obvious, and has been demonstrated, that such techniques (where the compressed data is re-compressed as many times as possible, dramatically reducing the file size) are impossible; indeed, there would be no bijection between the set of all random data and the compressed data. So why does this feel like it would be possible?
Even if the technique is not perfect as of yet, it can obviously be optimized and strongly improved. Why is this not more widely known/studied? If indeed these claims and experimental results are true, couldn't this revolutionalize computing?

always compress random data sets by more than 50%

That's impossible. You can't compress random data, you need some structure to take advantage of. Compression must be reversible, so you can't possibly compress everything by 50% because there are far less strings of length $n/2$ than there are of length $n$.

There are some major issues with the paper:

They use 10 test files without any indication of their content. Is the data really random? How were they generated?
They claim to achieve compression ratios of at least 50%, while their test data shows they achieve at most 50%.

  This algorithm defines a lossless strategy which makes use of the prime numbers present in the decimal number
  system

What? Prime numbers are prime numbers regardless of the base.
Issue #1 with decompression: prime factorization is a hard problem, how do they do it efficiently?
Issue #2 with decompression (this is the kicker): they multiply the prime numbers together, but doing so you lose any information about the order, since $2\cdot 5 = 10 = 5\cdot 2$. I don't think it is possible to decompress at all using their technique.

I don't think this paper is very good.


Sorting an unordered pile of items into drawers with minimal drawer movements A while ago, I was doing my laundry late at night.  When I brought my laundry back to my dorm, I started to put it away.

My wardrobe is set up as follows:

My drawers are categorized by the type of clothing they hold, and I'm very particular about that; this means I can't put t-shirts in my pants drawer (otherwise I'll be too flustered over it to sleep).  Of course, I know this categorization, and I know which drawer is which even in the dark.
I have $N$ pieces of clean laundry, and $M$ drawers arranged vertically (with the drawer at the top being $D_0$)
I can open and close drawers as I see fit, but if drawer $D_i$ is open, I can't put any clothes in drawer $D_{i+1}$ (because it's blocked by $D_i$).
All of my drawers are already closed when I enter the room.
When I finish, I have to close all open drawers.

Considerate gentleman that I am, I don't want to wake up my roommate (this was a college dorm, so we slept in the same room).  I resolved to not turn on the lights and make as little noise as possible.

This means that I have to put away my laundry under the following constraints:

I can't see into my laundry bag, so I only know what I grab as soon as I pull it out.
Opening and closing a drawer makes noise.  Pulling items out of my laundry bag, or actually putting them in the drawer, does not.
I can only put away one item of clothing at a time; I can't fold like clothes and put them in piles (and then put those piles away) because the floor's too dirty and there's no space on the furniture within reach of me.
I can put an item of clothing back in my bag and take out another, but the one I take out next could be the one I had just put back in (remember, I have no control over what I pull out of the bag).

Given this, I have three questions:

How can I put my laundry away while opening and closing the drawers as few times as possible?
Has anyone else thought of this problem or something similar?
Does this problem have any practical applications?

How about the following:

Go through your bag; fold and stack items for drawers $D_i$ and
$D_{i+1}$, $i \in 2\mathbb{N}$, in/on drawer $D_i$
(which you open on demand).

Make sure you have the items for $D_{i+1}$ on top; that may require quite
some reordering pancake-style,
but you don't seem concerned about such operations.

Note that there is always enough room (two drawer heights) to do this,
assuming the drawers are roughly equal and your clothes fit into them as it is.
For each open drawer $D_i$,

pick up the stack for $D_{i+1}$ (and put in the bag, if necessary),
close $D_i$,
open $D_{i+1}$,
put the stack in there, and
close $D_{i+1}$.

This algorithm requires $2M$ drawer movements if all drawers get clothing, so it is worst-case optimal.

It will waste some movements if there are items for $D_{i+1}$ but not $D_i$; if only odd drawers get items, we execute twice the drawer movements necessary. Since this is the worst that can happen, we still have a $2$-approximation.


What is the optimal solution of the 1962 Procter and Gamble's TSP Contest? In 1962, you could win a prize of \$ 10 000 (about \$ 80 000 in today's money) if you found the solution to an Euclidean travelling salesman problem defined on 33 cities.

http://www.math.uwaterloo.ca/tsp/history/pictorial/car54.html

Looking at the picture, the problem seems pretty easy. However I failed to find more detailed resources on the problem.

Does anybody know some more details, such as the exact distances and an optimal solution?

Full details are in Robert L. Karg and James L. Thompson, A Heuristic Approach to Solving Traveling Salesman Problems (Management Science, 10(2):225–248, 1964).  The PDF is available from JStor and Informs.org (both paywalled). This is the paper that produced the optimal tour of 10,861 miles. It also includes the full distance table but I'll not reproduce that here as it's way too much typing.

The solution is also illustrated on page 15 of The Traveling Salesman Problem by David L. Applegate, Robert E. Bixby, Vasek Chvátal and William J. Cook (Princeton University Press, 2007). The introduction to that book, which includes the relevant page, is freely available from the publisher.


Partitioning a set so both parts have sum at least $c$ times the total sum Let $c\in(0,1/2]$ be a constant. Given a set of positive integers with sum $S$, is there a partition into two subsets such that both subsets have sum at least $cS$?

If $c=1/2$, this is the famous partition problem which is NP-complete. What is known about the complexity for other values of $c$?

I posted the question to CS Theory several weeks ago. The only response was a comment that claimed that the problem is NP-hard, but the commenter never responded to my request for a  proof or reference.

The problem is polynomial (even linear time) for any fixed $c < 1/2$.

Assume no there is no item of size $> (1-c)S$, otherwise it is a trivial no-instance.

If there is any item $w_i$ with size $\geq cS$ we are immediately done because we can take one half of the partition to be that item.

Otherwise, all items are $< cS$. Greedily taking items means we will exceed the target sum by less than $c S$, meaning the remaining items have weight at least $(1-2c)S$. If $c\leq 1/3$, the instance trivially is a yes-instance.

For $c>1/3$, note that for the items smaller than $(1-2c)S$, we can use a greedy algorithm to assign them after we have a correct(*) solution for the large items. The number of large items is at most $1/(1-2c)$, which, for fixed $c<1/2$, is a constant. Thus, we can guess (in constant time) a solution for the large items, then use a greedy algorithm to distribute the small items. Note that the constant tends to infinity as $c$ tends to $1/2$.

(*) Where correct means neither half of the partition exceeds $cS$ by more than $(1-2c)S$.


Boolean Algebra Simplifying complex equation I am trying to simplify the following equation and I am getting stuck on a line and I can't cut it down any further. I'm not sure if certain 'moves' are legal or not.

F(A,B,C,D) = A'B'C' +ACD + A’BCD + A’BC’ + ABC + AB’CD'

After regrouping I got:
A'(B'C' + BCD + BC') + A(CD + BC + B'CD')

I thought right after this you'd get 1 because A + A' is 1 and then after that you would get each term in parentheses leftover as the final expression. Is that right?

Whenever you are faced with two Boolean expressions $f,g$ on $n$ variables and wish to know whether they are equivalent, there is a simple algorithm you can apply:

  Go over all $2^n$ possible truth assignments, and check whether $f$ and $g$ have the same truth value on each.

While this is infeasible for large $n$, in your case $n = 4$, so there are only 16 many truth assignments to check; in fact, you could even do this by hand, though it might be less error-prone if you programmed it.

Using this approach, you should be able to tell whether your simplification is valid.


A problem about slicing and indexing in numpy in Python I learned that in numpy, given a vector, slicing and indexing could give different results. I ran the following codes:

a = np.array([1, 2])
b = np.array([3, 4, 5])
print(b[a])
c = b[1:]
print(b)
c[0] = 1
print(b)
print(c)
print(b[1:] is c)

and get the result:

[4 5]
[3 4 5]
[3 1 5]
[1 5]
False

Since when I modify c, b is also changed, that means I should have a True in the last line right? Why it is not the case?

Thank you for any help!

When you slice a Numpy array, you get a special "slice" object, which holds pointers back into the array it was taken from. So if you do the same slicing operation twice, you'll get two different slice objects, which contain pointers to the same array in memory. (If you compare them using == instead of is, you'll see they compare equal, even though they're different objects.)

You can get the same effect with memoryviews, which are in the standard library. Each memoryview is its own object with its own address, but many memoryviews can point into the same data structure.


Operations on asymptotic notations How to use algebra in operations that involve asymptotic notation?
Like for example:

$C_1(n)= O(n)$
$C_2(n) = O(n^2)$
Is $C_2(n)/C_1(n) = O(n)$?

Yes and no.

A function $f(n)$ is said to be $O(g(n))$ if there exists a constant $c$ such that

$$
\lim_{n\rightarrow \infty}\dfrac{f(n)}{g(n)} \leq c
$$

Knowing this, a few things immediately become apparent:

Addition and subtraction preserves the largest $O$ of the result, thanks to the properties of limits.

For instance, $f(n) \pm h(n)$ are $O(g(n))$ if both $f$ and $h$ are
individually $O(g(n))$.

This is why you can say, if two operations are $O(n)$, then the resulting sum/subtraction is also $O(n)$.

If either $f$ or $h$ were $O(n^{2})$, then the result would be $O(n^{2})$. This is in agreement with intuition.
A function that is $O(n)$ is also $O(n^{2}), O(n^{3})$, etc. as you can prove by this definition.

For practical purposes, that is immaterial, as you only usually care about the smallest upper bound.
Multiplication can be simplified in the manner you require.

For instance, say I have $f, h$ that are both $O(n)$. This means

$$
   \lim_{n \rightarrow \infty}\dfrac{f(n)}{n} < c\;\;\mathrm{and} \; \; \lim_{n \rightarrow \infty}\dfrac{h(n)}{n} < c
   $$

or, equivalently,

$$
   \lim_{n \rightarrow \infty} f(n) < \lim_{n\rightarrow \infty} cn\;\;\mathrm{and} \; \; \lim_{n \rightarrow \infty}h(n) < \lim_{n\rightarrow \infty} cn
   $$

I can then argue that $f \times h$ is $O(n^{2})$, since, when we go to calculate it, this would require:

$$
       \lim_{n\rightarrow \infty}\dfrac{f \times h}{n^{2}} < c
   $$

which we can prove like so by substituting the inequalities above:

$$
       \lim_{n\rightarrow \infty}\dfrac{f \times h}{n^{2}} < \lim_{n\rightarrow \infty} \dfrac{cn \times cn}{n^{2}} < c^{2}\;\;\mathrm{which\;is\;a\;constant!}
   $$

In general, the product of two polynomial operations of order $O(n^{k}), O(n^{p})$ is at least $O(n^{k+p})$.
Division is a bit trickier. Let's take your example: say we have $f, h$ both $O(n)$.

We now try to calculate the limit, using the properties formally stated above, and find:

$$
   \lim_{n \rightarrow \infty}\dfrac{\frac{f}{h}}{n} < \lim_{n \rightarrow \infty} \dfrac{\frac{cn}{cn}}{n} < lim_{n \rightarrow \infty} \dfrac{1}{n} = 0 < c
   $$

so it is $O(n)$.

But wait a minute! It is also $O(1)$:

$$
   \lim_{n \rightarrow \infty}\dfrac{\frac{f}{h}}{1} < \lim_{n \rightarrow \infty} \dfrac{\frac{cn}{cn}}{1} < lim_{n \rightarrow \infty} \dfrac{1}{1} = 1 < c
   $$

so the same operation is somehow both $O(1)$ and $O(n)$ at the same time.

No, this is not some quantum spookiness at work. Remember that a function that is $O(n^{c})$ is also $O(n^{k})$ if $k > c$, as we stated above. Correctly speaking, it is not wrong to say either $O(1)$ or $O(n)$ or any other higher power (excluding deities).

In such cases, you may want to use the much stronger $\theta$ definition, which says a function $f$ is $\theta(g(n))$ if $f(n)$ is $O(g(n))$ and $g(n)$ is $O(f(n))$ i.e. they grow at the same pace.


Consistent heuristic and A* The following graph has consistent heuristic.

An A* algorithm will alter its first guess ACD to the correct shortest path ABD... if it has consistent heuristic, doesnt it mean, that AB should be found before AC?

A* isn't finished until all nodes with $f(n) < f(goal)$ are expanded.

So even though you have added $D$ to the open set you still need to expand $B$ because $f(B) = 11 < f(D) = 17$ after which $f(D)$ will become $12$


Why does appending permutations of servers at the end of hash table avoid bottlenecks? I was reading the following FDS paper:

https://www.usenix.org/system/files/conference/osdi12/osdi12-final-75.pdf

The paper has a TLT (tract locator table) for identifying where to write in each server. The table is basically a hash table where the index i maps to some (tract) server to do writes to or reads to.

Say that there are n (tract) servers. It says that if instead of just having index i mapping to server i, if instead we appended n more indexes mapping to some permutation of the servers (and having a table of size 2n in this example), we can avoid having a bottleneck at any specific server when doing reads or writes. Basically it claims that as we append more permutations the better. Why is this?

Why would this be?

Just for reference the index mapping function is:

$$i = (hash(g) + t) \pmod n$$

where:

g = is the global UID for a blob

t = tract number. (tract is the measure/units of reads and writes to a blob).

n = is the number of tract servers or a multiple of the tract servers.

hash = SHA-1 (according to the paper)

Paper Reference:

Title: Flat Datacenter Storage

Author(s): Edmund B. Nightingale, Jeremy Elson, Jinliang Fan, Owen Hofmann, Jon Howell, Yutaka Suzue

Institution(s): Microsoft Research, Univeristy of Texas at Austin

Adding permutations isn't about preventing slow servers from becoming bottlenecks, rather it's about dispersing a convoy once one forms behind a slow server.  Because of the way tract locations are hashed, sequential reads of any blob always walk the tract locator table in the same order.  Suppose you have six tract servers and your tract locator table looks like this

123456

and server 3 is slower than the others.  Since sequential readers walk the table in the same order the slowness of server 3 will cause a convoy of sequential clients to form waiting for server 3.  Once server 3 serves them, they all move on server 4 which may also become overloaded.  Then 5, then 6, and before long the convoy is big enough to hammer each server in turn instead of spreading the load evenly across all of them.

If your tract locator table looks like this

643512623154125364213546

i.e. four permutations of 123456, events transpire differently if there is a slow server.  If server 3 is slow, satisfied sequential readers will move from server 3 to servers 5, 1 or 6 depending on where they are in the table.  This instead of all sequential I/O clients turning their attention to the same server after visiting server 3.  The extra permutations have the effect of breaking up convoys if they form and lessening the likelihood of convoys forming at all.


Finding the maximum substring for which a given predicate is true Given a string $S$ of length $N$ and a string predicate $F$, find the maximum substring, $s$, such that $F(s) = \text{true}$.  Assume that $F$ satisfies the following:

If $F(g) = \text{true}$, then any proper sub-string of $g$, above a certain cutoff length $L$, also evaluates true.
Strings below the cutoff length evaluate to false

What is the best strategy to find $s$ which minimizes the function evaluations?

Naive approaches:

Sequential search of the string $\mathcal{O}(N^2)$ function evaluations.

I suspect there must be a better way but anything I look up just sends me to Kadane's algorithm.  I would appreciate it if anyone has any references which might be useful or know the answer.

Let's denote $[\exists s: F(s) \wedge |s| = x]$ as $B(x)$. First property of $F$ implies that for any $x > L$

$$B(x) \implies B(x-1)$$

Which by induction implies:

$$B(x) \implies \forall i \in [L, x] : B(i)$$

In other words, if you know that $B(x)$ is true, you don't have to examine lower values of $x$. And if $B(y)$ is false, you know that higher values of $y$ can't give you true, as it would contradict that $B(y)$ is false.

Now you can find maximal $x$ (such that $B(x)$ holds) using binary search. For each iteration of the search, $B(i)$ can be verified in $\mathcal{O}(N)$ calls to $F$: you just need to call it for every substring of fixed length $i$.

In total, this gives you $\mathcal{O}(N \log N)$ calls to $F$.


Approximation factor of NP-complete problems We talked about the following theorem in class but I am still having problems to understand it:

For a NP-complete decision problem "Does a valid solution with a value $\leq K$ exist?" there is no approximation algorithm for the corresponding minimization problem with an approximation factor $\lt 1 + 1/K$.

Why is this necessarily true? And where does that upper bound $1 + 1/K$ come from?

The crucial assumption here is that the value is an integer.

If the value is an integer, then telling whether there is a valid solution with value $\le 10$ is as hard as telling whether there is a valid solution with value $\le 10.999$ (it's the question).  Thus, you shouldn't expect a polynomial-time approximation algorithm with approximation factor $10.999/10$ or better -- if you had such an approximation algorithm, you could tell whether there was a valid solution with value $\le 10.999$, which would tell you whether there is a valid solution with value $\le 10$, which would let you solve the original problem, which would mean that you have found a polynomial-time algorithm for a NP-complete problem.  That would be unexpected.