# Question
Title: Time Complexity and Optimization for the Algorithm?
I have found a algorithm to check whether a Hamiltonian Cycle Exists in the graph or not, but not able to compute/analyse it's time complexity.

The algorithm is as follows :

1. Label all the vertices with distinct prime numbers.
2. Label all edges with weight equal to 1.
3. Now remove one vertex at a time, while removing a vertex v, if there is edge between u and v & v and w, then add a edge between u and w, with weight = weight(u-\>v)\*weight(v-\>w)\*label(v)
4. If at the end you end up with only one vertex with self edges and if there is a self edge that is equal to the product of all the primes of the removed vertices then there is Hamiltonian Cycle.

I have proved the algorithm is correct but unable to find it's time complexity. I think there can be much more optimization in this algorithm also, as we don't need to add those edges to the graph that whose weight divides the weight of some other already present edge. If someone can give some optimization to this algorithm it may turn out to be polynomial, thus proving P = NP.

# Answer
Unfortunately, whenever you start thinking about algorithms that use the nice prime factorization property things start breaking down. Why? You never said *how* you could generate $n$ prime numbers. That is not $\in P$, in fact that is still an open problem in mathematics, how many prime numbers are there? So even though the algorithm amy be suitable for small input sizes it is not theoretically sound.
> -3 votes

---
Tags: time-complexity, np-complete, optimization, p-vs-np
---


title: ∅-free regular expressions?

text:
# Question
Title: ∅-free regular expressions?
This is a question involving regular expressions for regular languages.

I am currently stuck trying to prove that the operand ∅ is not necessary unless the language is the empty set. That is, a regular expression is either equivalent to ∅ or is a ∅-free regular language. (A language is ∅ free if it contains no occurences of ∅)

This seems to be an induction proof, but I'm not really sure how to prove this. It seems like you're possibly trying to show that if a set is ∅ free, then doing anything involving ∅ will either result in the language ∅ or a ∅ free language.

So if r is ∅ free, then (r+∅) = r, r∅=∅ etc

I'm not really sure if this is really complete. I'm not overly comfortable with regular languages yet, so any help is much appreciated.

# Answer
> 3 votes
Preforming the proof by induction on the structure of the tree is good way to go about this. I like to think about how I would write a program to remove them because this directly leads to a constructive proof.

Say our regular expressions have the following form

$$ \begin{align} regex ::=& \\,\\, regex \\,\\, regex \\ |& \\,\\, regex^\* \\ |& \\,\\, regex^+ \\ |& \\,\\, regex\\,? \\ |& \\,\\, regex + regex \\ |& \\,\\, char \\ |& \\,\\, \varnothing \end{align} $$

The bases cases are the cases in which the regex is either a character or $\varnothing$

To give an inductive step say we have a regular expression of the form $regex + regex$. We can then recursively convert the two sub parts to regular expressions which either are the empty set or contain no empty set. So we have 4 cases

case 1: Both expressions contain no $\varnothing$ in which case we are done

case 2/3/4: One of the sides (possibly both) is $\varnothing$ so we remove that side. One needs to prove that this is valid but it isn't hard.

all the cases are going to precede as such with different proofs that the empty set can be eliminated.

---
Tags: regular-languages, regular-expressions
---


title: How ram is divided

text:
# Question
Title: How ram is divided
when I write a program, in a Von Neumann architecture, how the ram will be divided to receive data and instructions? For example if I have 1 MB of ram, the addresses from 0 to 499.999 for data and from 500.000 to 999.999 for instructions? Or I could find instructions mixed with data? Is divided the entire memory for example a side for all data of all programs and the other from all the instructions of all programs or when I load the memory with a single program, is reserved a small space (just for that program) and then that space is divided? Is the compiler to decide or the OS? Thanks in advance

# Answer
> 2 votes
> Is the compiler to decide or the OS?

The architecture put some constraints, then the OS is built to work within these and adds its own constraints, then the compiler does the same thing.

> how the ram will be divided to receive data and instructions?

It depends.

> Or I could find instructions mixed with data?

You could very well. It's more or less a defining property of Von Neumann architectures.

> Is divided the entire memory for example a side for all data of all programs and the other from all the instructions of all programs

That would be rare.

> or when I load the memory with a single program, is reserved a small space (just for that program) and then that space is divided?

That's more the case. But you seem to forget segmentation and paging which make it so that the addresses that a program see are not the physical one and what a program see as continuous may be physically interleaved with the memory of other programs.

---
Tags: memory-management
---


# Question
Title: Finding a lower bound for the amount of comparisons for sorting $k$ subarrays with $\frac n k$ elements
> Let the input be an array of $n$ elements, with $k$ sets $S\_1,...,S\_k$ such that each set has $\frac n k$ elements. The elements in each $S\_i$ are larger than the elements in $S\_{i-1}$.
>
> 1. Find an algorithm that sorts the input in $O(n\log (\frac n k ))$ runtime.
> 2. Find a lower bound for the minimal amount of comparisons in the worst case.

1. is pretty simple I think:

```
for each S_i
   mergesort(S_i[n/k])

```

But with 2. I get results that can't be right: in the worst case there would have to be at least $(\frac n k )!$ comparisons for each $S\_i$ because the algorithm will have to pass each combination at least once, also, this is the amount of leaves at the lowest level of the decision tree.

This gives: $T\_{worst}(n) = \Omega (k(\frac n k )!)$ which is a lot larger than $O(n\log (\frac n k ))$. So what am I doing wrong here?

# Answer
If a decision tree has at least $m$ leaves then its height is at least $\log\_2 m$. It is the height that bounds the number of comparisons rather than the number of leaves. In your case there are $(n/k)!^k$ leaves, and so $\Omega(\log\[(n/k)!^k\]) = \Omega(n\log(n/k))$ comparisons.
> 3 votes

---
Tags: algorithms, algorithm-analysis, data-structures, asymptotics, sorting
---


# Question
Title: Is there a known maximum for how much a string of 0's and 1's can be compressed?
A long time ago I read a newspaper article where a professor of some sort said that in the future we will be able to compress data to just two bits (or something like that).

This is of course not correct (and it could be that my memory of what he exactly stated is not correct). Understandably it would not be practical to compress ***any*** string of 0's and 1's to just two bits because (even if it was technically possible), too many different kind of strings would end up compressing to the same two bits (since we only have '01' and '10' to choose from).

Anyway, this got me thinking about the feasibility of compressing an arbitrary length string of 0's and 1's according to some scheme. For this kind of string, is there a known relationship between the string length (ratio between 0's and 1's probably does not matter) and maximum compression?

In other words, is there a way to determine what is the minimum (smallest possible) length that a string of 0's and 1's can be compressed to?

(Here I am interested in the mathematical maximum compression, not what is currently technically possible.)

# Answer
Kolmogorov complexity is one approach for formalizing this mathematically. Unfortunately, computing the Kolmogorov complexity of a string is an uncomputable problem. See also: Approximating the Kolmogorov complexity.

It's possible to get better results if you analyze the *source* of the string rather than *the string itself*. In other words, often the source can be modelled as a probabilistic process, that randomly chooses a string somehow, according to some distribution. The entropy of that distribution then tells you the mathematically best possible compression (up to some small additive constant).

---

On the impossibility of perfect compression, you might also be interested in the following.
> 47 votes

# Answer
For any given string there is a compression scheme that compresses it to the empty string. Hence it is not meaningful to ask how much a *single* string can be compressed, but rather how much a *collection* (or *distribution*) of strings can be compressed to, on average. In general, given a collection of $N$ strings, any compression scheme needs at least $\log\_2 N$ bits or so to encode a string from the collection in the worst case.

Also, in many cases we don't care about *exact* reconstruction. This is called *lossy compression*, and is how music and videos are compressed. In this case the lower bound stated above doesn't hold, but you can come up with other lower bounds.
> 35 votes

# Answer
Here's a simple scheme that can compress arbitrary bit strings lossless, with the smallest result being just one bit:

IF the string is an identical match for the recording of Beethoven's 9th symphony, fourth movement, in AAC format that is stored on my computer's hard drive, then the output is a single bit '0'.

IF the string is anything else, then the output is a single bit '1', followed by an identical copy of the original string.

This scheme reduces *one* possible input to exactly one bit, and increases every other input in length. There is a general principle: If a compression algorithm can map any input string to a compressed string, and there is a matching decompression algorithm that maps any compressed string back to the original string, and the compression algorithm maps *any* input to a shorter string, then it must map *some* input strings to longer strings.
> 27 votes

# Answer
For every compression scheme you can come up with, it is possible to produce data that will be uncompressible by it. So even if your compression scheme is very efficient with some types of data, it will never consistently compress to a certain ratio.

The way to produce an example of uncompressible data for a particular compression algorithm is simple: take any kind of data and run it through the compression algorithm repeatedly, until the size no longer decreases.

So the compressibility of a string of bits is not really a function of the length of the string, but of its complexity in relation to the compression algorithm.
> 6 votes

# Answer
There is an interesting and completely different algorithm that is used by enterprise backup systems. The idea is that if you have a company with 10,000 computers, then many many of these computers will contain many identical files. For example an email sent to everyone in the company might end up as an identical file on every single hard drive.

So a backup system trying to backup a file should obviously try to compress the file to save space, but first the backup system checks if an absolutely identical file is already saved! So instead of backing up *anything*, all that the backup system does is for example remembering that you have file number 1,487,578 on the backup system on your hard drive.

This is especially efficient for example when 10,000 users all have identical operating system and applications installed. For single users it's not very useful at all.
> -2 votes

---
Tags: data-compression
---


# Question
Title: Methods in Java with/without return? Simple but new to coding
I want to make this program below but I'm not sure how i would start them. Would i use methods with or without return? I have this due tomorrow and cannot figure it out. I've wrote the code multiple times but ended up deleteing it all.

```
    Part 1:
    Allow user to enter one character (L or S) and three integers between 100 and 1000.
    The program should output the following:
    1.  Display the message: “Wrong input!” if the numbers are not included in the interval [100-1000] using method CheckInput;
    2.  The largest number if the user enters the letter L, using method Largest;
    3.  The smallest number if the user enters the letter S, using method Smallest;
    4.  All numbers and their digits reversed using the method Backwards;
    5.  Using the method EvenOrOdd that takes one integer and outputs ‘True’ if the number is even or ‘False’ if it is odd, output the numbers entered followed by ‘True’ or ‘False’
    6.  Use the method CheckDivisor, that takes all three numbers and checks if the first number is a divisor of the second or third, and returns ‘True’ or ‘False’
    7.  Make the output easier to understand and add two more methods to the program

    Part 2:
    Write a program that allows the user to enter 3 words
    1.  Using the method Alphabetical output the three words in alphabetical order
    2.  In the main program concatenate(join) the three words, in alphabetical order in one variable ALL and using the method Mix replace all vowels by x
    3.  Call method First2Last2 to show the first and last 2 characters of the variable ALL, only if ALL has more than 4 characters, otherwise output the message “Invalid command!”
    4.  Call method Middlexx to insert xx right in the middle of the word ALL if the number of characters in ALL is even; otherwise replace the middle letter by yy

```

This is what a method with return looks like:

```
class method2{
 int perimeter(int L, int W){
int peri=2*(L+W);
return peri;
}
public static void main(String str[]){
method2 m = new method2();
System.out.print(10+""+5+"" + m.perimeter(10,5));
}}

```

Without return:

```
class method1{
void perimeter(int L, int W){

int peri=2*(L+W);
System.out.println(L+"\t"+W+"\t"+peri);
}
public static void main(String str[]){
method1 m = new method1();
m.perimeter(10,5);
}}

```

# Answer
> 2 votes
You only need to use a return if you plan to return a value or object to the caller. So for instance if you called a method, that then performed a calculation such as an addition you could return the result of that calculation. If you do not need to return anything to the caller then you do not need to use a return.

---
Tags: java
---


title: How to draw a DFA for given language?

text:
# Question
Title: How to draw a DFA for given language?
Give a finite state diagram for a DFA that accepts any word in the language $L = \\{w \mid w \in \\{a, b\\}^\* \text{ and }w \text{ alternates } a\text{'s and }b\text{’s and has an even number of }b\text{’s}\\}$.

My attempt: I am having problem on how to deal with the even part of b.

# Answer
> 1 votes
Since the strings must be of the form $ababab\dotsm$, and also there must be 0, 2, 4, 6, ... $b$s, begin with four states, each of which "remembers" the input so far:

* $q\_0$: just saw an $a$ and have seen an even number of $b$s so far,
* $r\_0$: just saw a $b$ and have seen an odd number of $b$s so far,
* $q\_1$: just saw an $a$ and have seen an odd number of $b$s so far,
* $r\_1$: just saw a $b$ and have seen an even number of $b$s so far.

Then, it's clear that these states will have transitions in a cycle, with transitions:

* $\delta(q\_0, b) = r\_0$
* $\delta(r\_0, a) = q\_1$
* $\delta(q\_1, b) = r\_1$
* $\delta(r\_1, a) = q\_0$

and the other possibilities will either be undefined or lead to a trap state, depending on what model of a DFA you're accustomed to using. Now make a new start state $s$, with $\delta(s, a) = q\_0$ (since you've just seen an $a$ and have no $b$s yet), and, for similar reasons, define $\delta(s, b) = r\_0$. I'll leave it to you to decide which (two) of the states in the cycle of four states should be final.

There are systematic ways to do this kind of *product DFA*, but in this case, it's no simpler than this *ad hoc* construction.

---
Tags: automata, finite-automata, dfa
---


title: Is HAMPATH in NL/L?

text:
# Question
Title: Is HAMPATH in NL/L?
I know HAMPATH is NP complete problem. But is there a way to tell if it is either a NL or L problem? I tried searching a lot of places online but it feels like I am going nowhere. Thanks in advance for any leads

# Answer
We don't know whether HAMPATH belongs to L or to NL. However, since NL$\subseteq$P, if HAMPATH belonged to L or to NL then it would follow that P=NP, which is conjectured not to be the case. So probably HAMPATH doesn't belong to L or to NL.
> 1 votes

---
Tags: complexity-theory, graphs, space-complexity
---


# Question
Title: NP complete language having no Polytime decidable superset
Is there an NP complete language having no polytime decidable superset (apart from the set of all strings)?

# Answer
> 6 votes
No, assuming **P$\\,\neq\\,$NP**. Let $L$ be any **NP**-complete language over alphabet $\Sigma$ and let $N = \\{n\in\mathbb{N}\mid L\cap \Sigma^n\neq \Sigma^n\\}$, i.e., $N$ is the set of lengths such that at least one word of length $n$ is not in $L$.

Note that $N$ must be infinite. If not, it has some maximum element $m$ and $L = \big(L\cap \Sigma^{\leq m}\big) \cup \Sigma^{\>m}$, which is a regular language, since $L\cap\Sigma^{\leq m}$ is finite. So, in particular, $L$ is in **P**, contradicting the assumption that it is **NP**-complete (under the assumption that **P$\\,\neq\\,$NP**).

But now pick any $n\in N$ and let $L\_n = \big(L\cap \Sigma^{\leq n}\big)\cup\Sigma^{\>n}$. $L\_n$ is a strict superset of $L$ (because, for any $n\<n'\in N$, $L\_n$ contains all strings of length $n'$ but $L$ doesn't) and $L\_n\in\\,$**P** by the same argument as above.

# Answer
> 8 votes
A slightly simpler proof is to note that $\Sigma^\* \setminus \\{w\\}$ is polynomial-time decidable and a superset of any language $L$ where $w\notin L$. Formally:

Suppose $P\not = NP$ and let $L$ be some $NP$-complete language. Then there exist at least $2$ strings $v\not = w$ so that $v\not \in L, w\not \in L$ or $L$ would not be $NP$-complete (since $L$ would either be $\Sigma^\*$ or $\Sigma^\*\setminus L$ would be a singleton). Then $\Sigma^{\*}\setminus \\{w\\}$ is polynomially decidable and a superset of $L$ (since $v\in \Sigma^{\*}\setminus \\{w\\}$).

If $P=NP$ then every language that is not $\emptyset$ or $\Sigma^\*$ is $NP$-hard, so in particular $\Sigma^\* \setminus \\{x\\}$ is $NP$-complete (where $x$ is any string in $\Sigma^\*$). However, $\Sigma^\* \setminus \\{x\\}$ has no (proper) superset that is not $\Sigma^\*$. So if $P=NP$, there is a a language having no superset $\in P$ that is not $\Sigma^\*$.

---
Tags: complexity-theory, np-complete
---


# Question
Title: Why Bloom filter needs $\frac{m}{n}\ln{2}$ hash functions?
I show from Wikipedia that the optimal number of hash functions is:

> $k =\frac{m}{n}\ln{2}$.

However it's not obvious for me why, even after reading the Wikipedia article (such as the one on false positives). Anyone interested in explaining with simple words? :)

# Answer
> 4 votes
This is explained in Wikipedia. Given $n,m$, the false positive probability is $$ \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k. $$ This is the quantity we want to minimize. While the exact expression is hard to minimize exactly, we can use the approximation $$ \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k \approx (1-e^{-kn/m})^k, $$ which is good if $m$ is large. We can optimize the latter expression using calculus, and the result is some expression which is very close to $(m/n) \ln 2$. This is a calculation that I leave to you.

---
Tags: bloom-filters, hashing
---


title: What input does this NFA accept?

text:
# Question
Title: What input does this NFA accept?
I'm trying to find out what strings this NFA would accept. From what I understand, an empty string would work, as well as any string that has nothing but 0's. But for strings containing 1's, I'm a little unsure. It would seem that as long as any 1 in the string has a 0 on either side of it (ex. 0100 or 01010), it would be acceptable. Am I missing something here?

# Answer
> 0 votes
$(0+01)^\*(\epsilon+00)0^\*$
or
$(0^\*(01)^\*)^\*(0^\* + 000^\*)$

You generally want to remove all the states one by one until you're left with only one or two states(when the start is not a final state). Say, you want to remove a state $l$; look at all the predecessors $p\_i$ of $l$ and all the successors $s\_i$ of $l$. Now any edge from a pred can come to $l$, may loop on $l$ or not and then go to any $s\_i$.
Consequently, for each $p\_i$ remove the edge $p\_i \to l$ bearing the label (say) $A\_i$, and for each edge $l \to s\_i$ bearing the label say $B\_i$, introduce a new edge $p\_i \to s\_i$ with the label $A\_iL\*B\_i$ where $L$ is the label of the self-loop on $l$ (if any). For an already existing $p\_i \to s\_i$, add it to its label.

---
Tags: turing-machines, automata, finite-automata, nondeterminism
---


# Question
Title: How to prove a L=L(G) without knowing the L?
How does one prove L(G)=L if the language is not given and only the grammar G is given? If there is no pattern to be seen in the grammar that would create the strings w of a language L, how would you go about doing this?

# Answer
> 3 votes
In cases like this, where you have a grammar and want to guess what the language is, a good way is to approach the problem systematically, by trying to derive some short strings. For example, if you had a grammar $G$ like this, $$\begin{align} S &\rightarrow SA \tag{1}\\ S &\rightarrow \epsilon \tag{2}\\ A &\rightarrow aS \tag{3}\\ A &\rightarrow bA \tag{4}\\ A &\rightarrow \epsilon \tag{5} \end{align}$$ then here are a few derivations, where the relevant production is labeled: $$\begin{align} \epsilon&: S \stackrel{2}{\Longrightarrow}\epsilon\\ a&: S \stackrel{1}{\Longrightarrow} SA\stackrel{2}{\Longrightarrow}A\stackrel{3}{\Longrightarrow}aS\stackrel{1}{\Longrightarrow}a\\ b&: S \stackrel{1}{\Longrightarrow} SA\stackrel{2}{\Longrightarrow}A\stackrel{3}{\Longrightarrow}bA\stackrel{4}{\Longrightarrow}b\\ aa&: S \stackrel{1}{\Longrightarrow} SA\stackrel{1}{\Longrightarrow}SAA\stackrel{2}{\Longrightarrow}AA\stackrel{3}{\Longrightarrow}aSA\stackrel{1}{\Longrightarrow}aA\stackrel{3}{\Longrightarrow}aaS\stackrel{2}{\Longrightarrow}aa\\ \end{align}$$ If you try this for, say $ab,ba,bb$, you'll find that they're all in $L$ which prompts a guess that this grammar generates all strings over the alphabet $\\{a,b\\}$. This isn't too hard to show, by induction on the length of a string in the language.

The proof goes like this:

**Base**. Show that the length-0 string, $\epsilon\in L(G)$. (We've done this already.)

**Induction**. Let $w$ be any string of length $n\>0$. Our inductive hypothesis is that any shorter string, $z$ is in $L(G)$, i.e., there is a derivation $S\stackrel{\*}{\Longrightarrow}z$. Now either $w=za$ or $w=zb$. We'll do one case and leave the rest to you: $$ S\stackrel{1}{\Longrightarrow}SA\stackrel{3}{\Longrightarrow}SaS\stackrel{2}{\Longrightarrow}Sa\stackrel{\*}{\Longrightarrow}za = w $$ so $w\in L(G)$, as required.

---
Tags: formal-languages, context-free
---


# Question
Title: Languages that are not subset, but are union
Are there examples of regular languages $L\_1$ and $L\_2$, where $L\_1$ and $L\_2$ is not a subset of each other but that $(L\_1 \cup L\_2)^\* = L\_1^\* \cup L\_2^\*$ ?

# Answer
> 2 votes
Yes. Let $L\_1=\\{a\\}, L\_2=\\{\epsilon\\}$. Obviously both languages are regular and neither is a subset of the other. We then have $$ (L\_1\cup L\_2)^\*=(a+\epsilon)^\*=a^\* $$ and since $$ L\_1^\*=a^\*,\quad L\_2^\*=\epsilon^\*=\epsilon $$ we have $$ L\_1^\*\cup L\_2^\*=a^\*\cup \epsilon = a^\* $$

---
Tags: formal-languages, regular-languages, proof-techniques
---


# Question
Title: Proof for Transitivity of Weak Bisimulation ≈
I have already posted this question on the other page, but I was suggested to post it here as it might be more relevant.

I am currently following a course in concurrency theory and I am currently trying to prove that the Weak Bisimulation relation ≈ is an equivalence relation.

I have managed to prove cases for reflexivity and symmetry, however I can't seem to make the connection for transitivity. Does any one have any clues how can I go about this ?

I have tried the relation {(P,R) | ∃Q.P≈Q,and Q≈R} as my witness relation and then at one point I get stuck.

I assumed that P-\>a P' which gives me that there is Q =\>a Q' and that P' ≈ Q' Now the thing is that since Q =\>a Q' then by the definition of =\> Q -\>tau\* Q1 -\>a Q2 -\>tau\* Q' Q1 -\>a Q2 will cause some R1=\>a R2 such that Q2 ≈ R2 Then I am not sure how to proceed to show that somehow there is a transition R =\>a R' such that (P', R') are in R. May be I believe I have to use numerical induction on the number of tau ?

Thanks !

# Answer
> 2 votes
You are on the right track. It can be useful to prove the following lemma: if $\sim$ is a weak bisimulation, if $P\sim Q$ and if you have a sequence of transitions $P\xrightarrow{w}P'$ for $w\in (Act\cup\\{\tau\\})^\*$ then there must be a sequence $Q\xrightarrow{w'}Q'$ with $P'\sim Q'$ and $w =\_{\tau} w'$, i.e., $w$ and $w'$ are "the same modulo $\tau$". This can be done by induction on $w$, and it will come in handy when you deal with transitivity. Check that $u=\_\tau u'$ and $v=\_\tau v'$ imply $uv=\_\tau u'v'$, i.e., that $=\_\tau$ is a congruence.

---
Tags: concurrency
---


title: Efficient haircuts

text:
# Question
Title: Efficient haircuts
I have a real vector $v$. From this vector, I want to extract a sequence of integers, $ix$. The first integer is found by, $ix\_0=argmax(v)$. 1 is then subtracted from $v\_{ix\_0}$, and the process is repeated until all elements of v are less than 0.

The following pseudo-Python function does this.

```
def countdown(v):
    ix = []
    while True:
        ix_t = argmax(v)
        if v[ix_t]>0:
            v[ix_t]-=1
            ix.append(ix_t)
        else:
            break
    return ix

```

BUT, it is inefficient, because the argmax does a new scan over all the elements of v on every step. It seems like there must be a better way to represent v so that we can efficiently check what the new argmax should be without scanning over the whole vector from scratch. Any ideas?

# Answer
The exercise wants you to use a priority queue (also known as a heap). I'll let you figure out how this helps.

If the input were integral, then you could do even better by sorting the list. This might still work even in the general case, but requires more work. (You might need to sort both the values themselves and their fractional parts.)
> 3 votes

---
Tags: algorithms, data-structures, time-complexity, sorting, priority-queues
---


# Question
Title: /How/ is the machine code within the CPU physically implemented; /why/ precisely does this work; and /where/ is it stored?
I understand the concept that the CPU's machine code is what translates the binary input into commands, and then executes these commands, many billion times per second. I can understand how, **given this concept**, everything works -- breakneck calculations and a fantastically comprehensive codebook allow for advanced processes.

But explain to me why is this is given? In other words, if someone was pitching this idea to me as a mere concept, I would think they were absurd -- obviously it works, so please show me my error! **Why** does this work at all? **Where** is this codebook stored physically on the CPU, and beyond the mere logic of it, **how** does the codebook 'force,' so to speak, the physical hardware to 'obey' the commands that it translates? What is intimately going on here..? Is there a 'codebook' register that, when it reflects a specific code, 'decodes' this information by physically sending an electrical charge to a specific series of wires? How then does this work..?

I have read various resources, but all of them explain **how** the CPU works without explaining precisely **why** it does in a purely physical sense. Every resource escapes this by using an oddly anthropomorphizing analogy, or using an explanation laden with words that have no business being used to describe the automatic processes of machines like those 'quoted' above. Any straight-forward explanation or resources on this specific question would be greatly appreciated.

# Answer
This is a very broad question which would be far easier to answer in person with a whiteboard than in a short online missive.

I found this document for the design of a simple computer from Purdue (part of an engineering program assignment). The document shows the design of an 8 bit computer that would be far simpler to explain than your average CPU of today. It has a very simple "codebook" of only 6 instructions using a 3 bit opcode. More complex systems perform in a similar way, but with larger opcodes and more instructions.

The "codebook" in this example is decoded by logic gates (physical hardware) and referred to as the "Instruction Decoder and Micro-sequencer" in the document. This is a section of hardware that typically will take the instruction's opcode to determine how to sequence data through various parts of the computer in order to complete the intended instruction. This is done in stages based on a system clock and counting through different phases of an operation.
> 5 votes

# Answer
At a very basic level, the CPU implements a Boolean circuit with memory. That is, the basic building blocks of a CPU are *logic gates* (in practice, NAND gates) and *flip flops* (memory units). These are electrical creatures, and if you want to understand how they work physically, you'll have to study electromagnetism.

(Modern CPUs are quite a bit more complicated than that. They have cache memories and microcode that machine code is compiled to. But you can ignore these details to start with.)

The book The Elements of Computing Systems explains how to build a barebones CPU using NAND gates and flip-flops. Through the link you can find lecture notes, the first few of which explain how how to construct a CPU.
> 4 votes

---
Tags: memory-hardware, cpu
---


title: Why do puzzles like Masyu lie in NP?

text:
# Question
Title: Why do puzzles like Masyu lie in NP?
The puzzle is made up of (n x n) squares so when taking the problem the input size would be n.

Rules of Masyu:

* The goal is to draw a single continuous non-intersecting loop that properly passes through all circled cells. The loop must "enter" each cell it passes through from the center of one of its four sides and "exit" from a different side; all turns are therefore 90 degrees.
* White circles must be travelled straight through, but the loop must turn in the previous and/or next cell in its path.
* Black circles must be turned upon, but the loop must travel straight through the next and previous cells in its path.

# Answer
> 7 votes
Because a problem is in **NP** if, and only if, "yes" instances have *succinct certificates*. Informally, this means that the solution to any instance is at most polynomially large in the size of the instance, and if you're given an instance and something that is claimed to be a solution to it, you can check in polynomial time that it really is a solution.

More formally, a language $L\subseteq\Sigma^\*$ is in **NP** if, and only if, there is a relation $R\subseteq \Sigma^\*\times\Sigma^\*$ such that:

1. there is a polynomial $p$ such that, for all $(x,y)\in R$, $|y|\leq p(|x|)$;
2. the problem of determining whether $(x,y)\in R$ is in **P**;
3. $L = \\{x\mid \exists y\\,(x,y)\in R\\}$.

For example, consider graph 3-colourability. You can describe a graph on $n$ vertices just by writing out its adjacency matrix, which requires $n^2$ bits. If a graph is 3-colourable, you can describe a colouring in $2n$ bits: just list the colour of each vertex in turn (say, $00$ for red, $01$ for green, $10$ for blue). So, if a string $x$ describes a graph, and that graph is 3-colourable, each 3-colouring can be described in a string $y$ with length $2\sqrt{|x|}\leq 2|x|$. Furthermore, if I give you a decription of a graph and a description of a 3-colouring, you can easily check in polynomial time that it really is a 3-colouring: just check that adjacent vertices always have different colours. So, the relation $$\\{(x,y)\mid x\text{ describes a graph $G$ and $y$ describes a 3-colouring of }G\\}$$ proves that 3-colourability is in **NP**.

So, to show that Masyu is in **NP**, we just need to construct the corresponding relation $R$. We can describe an $n\times n$ instance of Masyu in $2n^2$ bits: for each square in turn, write $00$ if it's blank, $01$ if it contains a black circle and $10$ if it's a white circle. We can describe a solution in $3n^2$ bits: for each square in turn, write $000$ if the square isn't on the solution path, and $100$, $101$, $110$ and $111$ if it's on the path and the next square is the one to the right, left, up and down, respectively. It's easy to check in polynomial time that a claimed solution really is a solution: just find a square that's on the path, follow the path and check it satisfies the criteria.

---
Tags: complexity-theory, np-complete, proof-techniques, np
---


# Question
Title: Can adjacency lists be used in directed graphs?
I've been reading: https://en.wikipedia.org/wiki/Adjacency\_list

It says that that graph can be constructed with the list $\\{b, c\\}, \\{a, c\\}, \\{a, b\\}$.

However, what if I wanted to construct a directional list? Does $\\{b, c\\}$ point to $b$ or $c$?

How can you use a list to represent a directional graph?

# Answer
> 2 votes
Your graph is actually undirected. The notation is a list of *edges* in the graph. Since edges are undirected, each edge is a *set* of two vertices. Your lists contains three edges, since a triangle has three edges. It actually contains *all* possible edges involving the vertices $a,b,c$.

A *directed graph* is one in which edges consist of two *ordered* vertices. The edge points from the first vertex to the second. You can represent such a graph using a list of pairs.

*Adjacency lists* are a different data structure, which is described in the Wikipedia page you link to, so I skip its description here. It can be used for both undirected and directed graphs, in the natural way.

# Answer
> 2 votes
> Does $\\{b,c\\}$ point to $b$ or $c$?

Neither. The adjacency list representation of a graph, you are given, for each vertex $x$, a list of the vertices adjacent to $x$. Thus, the lists $\\{b,c\\}$, $\\{a,c\\}$, $\\{a,b\\}$, tell you that $a$ is adjacent to $b$ and $c$, $b$ is adjacent to $a$ and $c$ and $c$ $is$ adjacent to $a$ and $b$.

You shouldn't confuse this with the notation $\\{x,y\\}$ for the undirected edge connecting $x$ and $y$.

---
Tags: adjacency-matrix
---


# Question
Title: $A$ and $B$ are Turing-recognizable and their union is $\Sigma^*$, find a decidable $C$ with $A - B \subseteq C$ and $B - A \subseteq \overline{C}$
Sorry for long title - the question is a bit unwieldy. To state the question precisely, I'm wondering about the following proposition:

> Let $\Sigma = \\{0,1\\}$. If $A$ and $B$ are Turing-recognizable and $A \cup B = \Sigma^\*$, then there exists a Turing-decidable language $C$ such that $A \cap \overline{B} \subseteq C$ and $\overline{A} \cap B \subseteq \overline{C}$ (equivalently, $A - B \subseteq C$ and $B - A \subseteq \overline{C}$

So, my current train of thought is as follows. Because $A \cup B$ is $\Sigma^\*$, we have that $\Sigma^\*$ is partitioned into exactly three disjoint sets: $A - B$, $A \cap B$, and $B - A$. That is, given $x \in \Sigma^\*$, $x$ is in exactly one of these sets.

The basic way I can think of to obtain a decidable language is to enumerate one in lexicographic order (which always yields a decidable language). So one idea would be to enumerate $\Sigma^\*$ in lexicographic order, and print a string if and only if it is *not* in $B - A$, but that poses a problem because we would have to decide membership in $B - A$, but they are merely recognizable.

I've thought about enumerating $A$ and $B$ but since they're only recognizable, the enumerations could be in any arbitrary order, making it impossible to compare them to test for membership in $A-B$ or $B-A$.

Finally, I know that $A$ and $B$ (if they are infinite) have infinite decidable subsets, but I don't think that will help.

I'd appreciate some hints if anyone has any.

Edit: Missed a hypothesis that $\Sigma = \\{0,1\\}$, which I'm not sure is relevant (I wouldn't think so), but it might be.

# Answer
Got it. The question makes it seem more complicated than it really is.

Let $M$ and $N$ be TMs that recognize $A$ and $B$, respectively. Construct an enumerator $E$ that behaves as follows:

1. For each $s\_i \in \Sigma^\*$ (in lexicographic order):
2. Run $M$ and $N$ on $s\_i$ simultaneously. It must be the case that $s\_i$ is in *at least one* of $A$ or $B$. So, at least one machine is guaranteed to halt.
3. If $M$ halts, $s\_i \in A$, which means certainly $s\_i \not\in \overline{A} \cap B$, so print $s\_i$.
4. If $N$ halts, $s\_i \in B$, which means certainly $s\_i \not\in A \cap \overline{B}$, so do *not* print $s\_i$.

So $E$ prints *at least* all the strings in $A \cap \overline{B}$, and definitely does *not* print strings in $\overline{A} \cap B$. $E$ enumerates a language in lexicographic order, so its language is decidable and satisfies the conditions.
> 3 votes

# Answer
I believe 'C' is not also turing decideable. Consider the following 3 cases:

Case 1 : Intersection of A and B is empty set and neither of them is empty. Then A and B become Turing Decidable, therefore C also becomes turing decidable. Closure properties for TM.

Case 2: Intersection of A and B is either of them (Lets say A-B = A). Then, language (B-A) transforms to an undecidable, as its equivalent to the language which is empty. C = A-B = A, is Turing recognizable.

Case 3: Intersection of A and B is non-empty. Now, for C - TM for A should accept which would as its acceptor and TM for B should reject as it shouldnt belong to it. BUT since, B is an Turing recognizable(not decider) only (assuming from your query), it means it might never halt for the input which doesnt belongs to it. Thereby, the TM accepting C might never halts for strings belonging to C.Thereby, C doesnt have any acceptor.
> 0 votes

---
Tags: formal-languages, turing-machines
---


# Question
Title: Help wrapping my head around a combinatorial optimization problem
Here's the problem I'm trying to solve:

I have a bunch of widgets, whose weights vary over a small range. I would like to find the optimal grouping of them such that each group meets a minimum weight requirement, while maximizing the total number of groups I can form.

Knowing a specific name for this class of problem would be a good start. Help formalizing it would be even better. I did this stuff so long ago in school, I need my memory jogged good and hard. Thanks!

# Answer
> 1 votes
I recommend you use an integer linear programming (ILP) solver to approach this. It will be relatively easy to code this up, and the resulting solution will probably out-perform any other simple scheme I can think of.

Let $w\_1,\dots,w\_n$ be the (known) weights of your $n$ widgets. Let $t$ be the required minimum weight of each group. We're going to test whether it's possible to partition those $n$ widgets into $m$ groups, so that each group weighs at least $t$.

Here's how. Introduce zero-or-one variables $x\_{i,j}$. The intended meaning is that $x\_{i,j}=1$ means that widget $i$ is placed into group $j$. Add the following constraints:

* $\sum\_j x\_{i,j}=1$ for each $i$ (each widget can be placed in exactly one group).
* $\sum\_i w\_i x\_{i,j} \ge t$ for each $j$ (each group weighs at least $t$).

Now ask the solver whether the combination of these inequalities is feasible. If the ILP solver finds a feasible solution, then you know it is possible to partition the widgets into $m$ groups. If it says the problem is infeasible, you know it's not possible to partition the widgets into $m$ groups.

Now use binary search to find the largest value of $m$ for which a feasible solution exists.

Of course, your problem is a NP-hard problem, so you shouldn't expect an efficient solution that works for all parameters -- but you might find that the ILP-based solution works well enough for your problem.

---

Incidentally, you mention that a typical problem instance would have "1000 widgets, \[with\] weights ranging from 2-4 oz in .05 oz increments". This means that there are only 40 possible weights, so while you have 1000 widgets, there are effectively only 40 different types of widgets.

This kind of situation allows a more efficient solution. It is possible to adjust the above algorithm to handle this situation. Let $w\_1,\dots,w\_n$ be the weights of the $n$ types of widgets, and let $q\_1,\dots,q\_n$ be the quantities of each type of widgets (i.e., you have $q\_i$ widgets of weight $w\_i$).

Now you can use integer variables $x\_{i,j}$ that are not zero-or-one, but are constrained to be integers in the range $0 \le x\_{i,j} \le q\_i$. The intended meaning of $x\_{i,j}$ is that it counts the number of widgets of type $i$ that are placed into group $j$. You introduce the constraints

* $\sum\_j x\_{i,j} = q\_i$, and
* $\sum\_i w\_i x\_{i,j} \ge t$.

Everything proceeds as before. In this way, the number of variables fed to the ILP solver is greatly reduced, which will likely make the solving process a lot more efficient. I definitely recommend applying this optimization, if you want to solve the problem in practice.

# Answer
> 3 votes
Here is a complete MIP (Mixed Integer Programming) model that should do the trick. I just use some random data (weights) with 100 widgets and 50 possible bins. When solved the variable NumUsedBins gives the maximum number of bins and the variable x gives the assignment. The equation 'order' is to make sure we use lower numbered bins first. The strange statement about optcr is to tell the solver to solve to optimality (for very difficult problems you may want to stop at 5% or so).

With 1000 widgets this becomes somewhat difficult to solve to optimality.

# Answer
> -1 votes
The first thing I would do in order to solve this question is simplify it into a smaller problem: You have the weights and the min-weight requirement. Now try to match 2 weights in order to reach exactly the min-weight. My approach:

1. Store every number inside a set.
2. For each number `a` calculate `- ( a - mid_weight ) = b`. Then check if the set already has the number `b` in it.

Now in the second scenario the pairs don't have to exactly match the min-weight. My approach would be:

1. Store every number inside a set.
2. For each number `a` calculate its optimal partner `- ( a - mid_weight ) = b`. Then check the closest element matching b inside the set. In C++ you can find both partners (the partner lower to b and higher to b) using `std::set::lower_bounds` and `std::set::higher_bounds`.
3. Sort all the matching pairs according to their waisted weight from lower to higher: `a + b - min-weight = wasted-weight`. Then always choose the best pair and reevaluate any new pairs that had a or b as partner.

This is only a quick attempt at your problem, i'm not sure if it's optimal. You have to do the general case. For a similar problem look up 3sum (or 4sum). I hoped this helped a little bit at least.

---
Tags: combinatorics, linear-programming
---


# Question
Title: How do POMDPs and Dynamic Influence Diagrams differ?
To give some perspective, first consider the following diagram comparing Markov Chains, HMMs, MDPs, and POMDPs (I'm not sure who to credit for it).

```

                    Fully observable          Partially observable
                _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
               |                         |                           |
    no actions |      Markov chain       |           HMM             |
               |_ _ _ _ _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _ _ _|
               |                         |                           |
    actions    |          MDP            |          POMDP            |
               |_ _ _ _ _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _ _ _|

```

Recall that an HMM allows us to model probability distributions over a sequence of observations. *Bayesian networks* (not pictured) are a generalization of HMMs which model conditional distributions over sets of random variables (see here for a description). When modeling a problem over time, one appends a time index to the model resulting in a *dynamic Bayesian network*.

A tool known as a *dynamic influence diagram* extends dynamic Bayesian networks to decision-making problems through the inclusion of actions that can effect the evolution of the problem.

**My question is**: how do dynamic influence diagrams and POMDPs compare? On the surface they seem like they are modeling the same problem type. What sort of problems are amenable to each tool?

# Answer
> 1 votes
I'll quote from the paper "Interactive Dynamic influence diagrams" (DIDs) by Polich and Gmytrasiewicz (AAMAS 2007):

> A dynamic influence diagram is a computational representation of a POMDP.

They continue soon afterward:

> DIDs perform planning using a forward exploration technique known as reachability analysis. This technique explores the possible states of belief an agent may be in in the future, the likelihood of reaching each state of belief, and the expected utility of each belief state. The agent then adopts the plan which maximizes the expected utility. DIDs provide exact solutions for finite horizon POMDP problems, and finite look-ahead approximations for POMDPs of infinite horizon.

To me this suggests that DIDs are, as the authors state, one possible *representation* of a POMDP, to which a specific look-ahead type solution method is related to. As look-ahead is limited to approximate solutions for infinite horizon POMDPs, this also suggests that DIDs can not represent *every* POMDP.

---
Tags: probability-theory, decision-problem, hidden-markov-models
---


title: Matrix Max in less than O(n)

text:
# Question
Title: Matrix Max in less than O(n)
I am attempting to find the maximum value in a matrix (or 2d array) and want to find it in less than O(n) time. The easiest way, which results in O(n) run time, is an element wise search. If a better run time is possible, I would also like to find any values over a specific threshold in less than O(n) time. Is any of this possible?

I cannot re-sort and do a binary search or something along those lines as the ordering is important.

# Answer
If you don't know anything about the contents of the matrix (such as some kind of monotonicity property), linear time is the best you can do for a one-off search with a deterministic algorithm by a simple adversary argument: if you don't look at everything, then you can't distinguish between the cases where the maximum component is/isn't one of the ones you didn't look at. If you want to maintain max-information for a dynamic matrix, then there might be suitable preprocessing and maintenance (for example, a search tree) that can speed things up.
> 15 votes

---
Tags: algorithms, runtime-analysis, arrays
---


# Question
Title: Is how much memory a program needs computable?
We know that how much time a program needs is not computable.

Do we know how much memory a program needs is decidable?

# Answer
No, and there's a simple way to see it.

Suppose that there was a way to compute how much memory a program needs. What does it mean precisely? It would mean that there's a way to find, given an arbitrary program¹, a number $n$ such that the program can run on a machine with $n$ bits¹ of memory.

First snag: what about programs that require an infinite amount of memory? Our memory analyzer would have to return something like $\infty$ in that case. Ok, that's not too bad — we could have an analyzer that returns either a (finite) amount of memory or $\infty$. If the program needs an infinite amount of memory, it doesn't terminate (each step of computation can only access a finite amount of memory).

If the memory analyzer returns a finite amount $n$, then we can *run* the program in a machine with $n$ bits of memory. But a “machine with $n$ bits of memory” is a finite automaton! Deciding whether a finite automaton terminates is easy.

So our memory analyzer has let us decide whether the program terminates. Since this is impossible (it's the halting problem), the hypothesis that there's a way to compute how much memory a program needs is false. If you have a correct memory analyzer (i.e. one that returns $n$ or $\infty$ if a program can run in at most $n$ bits of memory) then there must be programs for which the analyzer returns $\infty$, yet the program could in fact run in a finite amount of memory.

¹ <sub> A program including all of its inputs! The amount of memory is a function of the inputs in general. </sub>
² <sub> You can use any unit, bits are just an example. That only changes the amount of memory from a finite number to a different finite number. </sub>
> 8 votes

# Answer
There's the notion of how much memory a program 'actually' needs - to consider. You would have to consider the programming language of the program being analyzed. I'm sure there are other factors as well, but in the end, it doesn't really matter.

If you acknowledge (and it has been proven) that it is impossible to know if a program will halt, then I think it should follow that it is equally undecidable how much memory it will require.

Consider the following line of pseudocode:

```
malloc(rand())

```

Here we asked for a random amount of memory to be allocated. Since it's impossible to know how much exactly this line of code will need, then likewise it is unknowable how much the entire program will need.

Therefore, I will make the statement, that if we can provide one example that contradicts the statement that it is decidable, then it is not (Turing) decidable.
> 1 votes

---
Tags: computability, undecidability, halting-problem
---


# Question
Title: Hardness of approximation: what decision problem is hard exactly?
Just a question for personal comprehension. Consider the following statement:

> It is NP-hard to approximate Set-Cover within a $(1 - \epsilon) \log n$ factor for any $0 \< \epsilon \< 1$.

Now, NP-hardness refers to decision problems.So what is NP-Hard exactly here ?

My guess is that the statement is equivalent to saying that the following problem is NP-hard (but I really ain't sure):

> Given a set cover instance $S$ and an integer $k$ with the guarantee that either $S$ admits a cover of size at most $k$, or $S$ has a cover of size at least $k \cdot (1 - \epsilon) \log n$, decide if $S$ has a cover of size at most $k$.

Note that I took set cover as an example, but my question is on problems that are said 'hard to approximate' in general.

# Answer
> 2 votes
Your guess is correct. The formal statement corresponding to the informal one goes like this:

> For every $\epsilon \> 0$ and every language $L$ in NP there exists a polytime reduction $f$ mapping instances of $L$ to instances of set cover $(F,m)$ (where $F$ is a set system and $m$ is the target number of sets) such that:
>
> * If $x \in L$ then $f(x)$ has a cover with $m$ sets, and
> * If $x \notin L$ then every cover of $f(x)$ requires at least $(1-\epsilon)\ln n \cdot m$ sets, where $n$ is the size of the universe.

For this more accurate version, see Claim 4.2 in Dana Moshkovitz, The projection games conjecture and the NP-hardness of $\ln n$-approximating set cover.

A statement claiming that a certain approximation problem is NP-hard to approximate better than some factor should always be interpreted in this way.

# Answer
> 3 votes
Most likely what is meant is the following statement:

If $P \ne NP$, then there is no polynomial-time approximation algorithm for Set-Cover that achieves a $(1-\epsilon) \log n$ approximation factor.

Or, equivalently: the existence of a polynomial-time approximation algorithm for Set-Cover that achieves a $(1-\epsilon) \log n$ approximation factor implies that $P=NP$.

---

Your proposed formulation at the end of your question might look tempting, but if you want to understand how to formalize the claim, I probably wouldn't suggest formalizing it that way -- that formulation introduces unfamiliar technical issues of its own. The problem you listed is a promise problem (it's not a decision problem). Promise problems are weird and some of your intuition that you've built up won't work quite right for promise problems. Promise problems are weird and counter-intuitive; if you want to build your intuition, often it's best to simply avoid them, rather than try to absorb the messy details involved in formalizing them.

---
Tags: complexity-theory, np-hard, approximation
---


# Question
Title: If c ∈ Σ denotes terminals, then is Y = Σ∖{c} the set of non-terminals?
If $c\in \Sigma$ denotes terminals, then is $Y=\Sigma \setminus \\{c\\}$ the set of non-terminals?

These notations are used here, p. 379. But I cannot find their definitions.

So what I'm asking is, is the above a reasonable interpretation?

# Answer
No. $\Sigma$ is the set of symbols that the strings in the two languages are over ("the alphabet"). So $c$ is one symbol, and $Y$ is the set of all the other symbols in the alphabet. These will *all* be terminals when the CFG is constructed in the proof.

What the theorem is saying is that if you have a context-free language $L$ that uses only symbols from $Y$, then $L$ is also regular if and only if the new language where you prepend a $c$ to every string in $L$ (i.e. $cL$) is also regular.

At this point there's no mention of a CFG, so there's no terminals or nonterminals. The proof is where the CFG is introduced as a consequence of $L$ being context-free. Note however that this proof is very very truncated, there's a lot of detail and reasoning left out, so it's a lot harder to follow than it should be if you don't already see the reason that the theorem is true. There's also a series of mistakes in it.
> 4 votes

---
Tags: formal-languages, formal-grammars, notation
---


# Question
Title: What is the sqrt(n)-approximation algorithm for set packing problem
The set packing problem is : Given a universe $U$ and a family $S$ of subsets of $U$, a packing is a subfamily $C\subseteq S$ of sets such that all sets in $C$ are pairwise disjoint, and the size of the packing is $|C|$. The goal is to find the $C$ where $|C|$ is maximum.

According to Wikipedia, there exists a $\sqrt{|U|}$-approximation algorithm for this problem. But it doesn't give a way to approach that, it seems that the way cannot be found on google as well.

# Answer
> 4 votes
See Viggo Kann's page on set packing. Viggo mentions two $\sqrt{|U|}$ algorithms:

* Unweighted case: Halldórsson, M. M., Kratochvíl, J., and Telle, J. A. (1998), "Independent sets with domination constraints", Proc. 25th Int. Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci. 1443, Springer-Verlag, 176-185.
* Weighted case: Halldórsson, M. M. (1999a), "Approximations of weighted independent set and hereditary subset problems", Proc. 5th Ann. Int. Conf. on Computing and Combinatorics, Lecture Notes in Comput. Sci., Springer-Verlag, 261-270.

I found this link on the first page of the Google search `set packing approximation algorithm`. I suggest that next time you spend some quality time with your favorite search engine, looking at all links in the first few pages.

---
Tags: approximation, packing
---


title: When do deadlocks occur?

text:
# Question
Title: When do deadlocks occur?
I was reading about deadlocks in Operating Systems. Where I came across two examples below.

> Circles with label $P\_x$ are processes. Squares with label $R\_x$ are resources. Each dot in the square represents single instance of resource type $R\_x$. An edge from $R\_x$ to $P\_x$ means an instance of resource $R\_x$ is allocated to process $P\_x$. An edge from $P\_x$ to $R\_x$ means the process $P\_x$ is waiting for getting an instance of resource $R\_x$ allocated.
>
> Now consider below two resource allocation graphs
>
> The example on left involves deadlock while the one on the right did not involved deadlock.

I can understand that in right-side figure, if $P\_2$ releases its instance of $R\_1$, it can be assigned to $P\_1$, breaking the circular wait. Or if $P\_4$ release its instance of $R\_2$, it can be assigned to $P\_3$, breaking the circular wait. However we cannot break circular wait in left-side figure.

While I can try out this on any given resource allocation graph and decide if there is deadlock or not, I want to know can we have a generalized rule for this which can tell ***what exactly it is which is contributing to the deadlock, especially in case of multiple instances of resources are there***. I did not found any reference / book speaking of this clearly. So after a bit of thinking I came up with following fact:

> If there are multiple instances of same resource, for deadlock to exist, for any combination of two processes, if both are allocated an instance of same resource, then both should be a part of at least one cycle.

In right-side figure above, there is no deadlock because

* processes $P\_2$ and $P\_3$ are allocated instances of $R\_1$, but they both are not part of any cycle
* similarly processes $P\_1$ and $P\_4$ are allocated instances of $R\_2$, but they both are not part of any cycle

In left-side figure above, there is a deadlock because

* processes $P\_1$ and $P\_2$ are allocated instances of resource $R\_3$ and are part of same cycle,$P\_1-R\_1-P\_2-R\_3-P\_3-R\_3-P\_1$

So am I correct with the above realization of fact? Or there are more aspects/conditions to the above fact (of when deadlock is present and when not) that I am missing?

What I am asking is if there is any other condition which if met, instead of the above one, will still result in the deadlock (in the context of multiple instances of resources and apart from four classic conditions of deadlock: mutual exclusion, no preemption, hold and wait and circular wait)?

# Answer
All 4 conditions must be satisfied at the same time.

* Hold and Wait
* Non-preemption of resources
* Mutual Exclusion
* Circular wait

**In case of single instance of resources:**

Cycle in resource allocation graph represents deadlock.

**In case of multiple instance of resources:**

Cycle in RAG doesn't mean deadlock. You must check in the same way as you did. Let me write clear steps.

* We need to identify a process, in the cycle, which can execute without any dependency and execute that.
* Release the resources held by process.
* Next check the process which has all the resources to execute and execute completely and release the resources held by it.
* Keep doing till all the processes are executed.
* If you can't execute all the processes this way, then there is deadlock.

Hope that helps!
> 4 votes

# Answer
Your logic follows, and falls in line with the need for a circular wait in a deadlock.
> 0 votes

# Answer
A different type of diagram and model may help in answering the question “is there any other condition which if met \[…\] will still result in the deadlock?” (“When do deadlocks occur?”, 2015).

Consider a Petri Net model of the process-resource system, based on the left resource allocation graph and the following assumptions:

1. Process P\_1 requires one unit of Resource R\_1 and one unit of Resource R\_3 to perform its task.
2. P\_2 requires one unit of R\_1 and two units of R\_3 to perform its task.
3. P\_3 requires two units of R\_3 to perform its task.
4. A process takes one unit of a resource at a time.
5. A process returns every unit of every resource it has taken at a time.
6. All processes run on a single processor. The processor can handle one and only one process at a time.

## Figure 1: A Petri Net Model Based on the Left Resource Allocation Graph -- with Deadlock

A deadlock occurs in a system if or when the system “keeps waiting” for one or more resources it needs but the resource or resources will never be available. There are two reasons why the resource or resources will never be available. First, the resource was taken but never returned. Second, there was never “enough resources” to begin with.

If the left allocation graph is in a state of deadlock, then Figure 1 is one possible model that can reach this state.

Assuming there is enough resources, one way to prevent a deadlock is for a process to release the resources it has taken if one or more of the other resources it needs are not available. Another way to prevent a deadlock would be for a process allocate the resources it needs only if all of the resources it needs are available; otherwise, the process should not allocate any of the resources. The Petri Net in Figure 2 was designed this way – resources are allocated at the same time to a process if and only if every resource needed by the process is available.

## Figure 2: A Petri Net Model for Allocating Resources without Deadlock

## Notes

For the PDF version, Figure 1 and Figure 2 are interactive, dynamic diagrams. You can step through each process and see the state changes – including the occurrence of deadlock in Figure 1.

Figure 1 can be initialized in two ways: no resource is allocated to any process, and the resource allocation based on the left resource allocation graph.

## References

When do deadlocks occur?” (2015). Computer Science Stack Exchange. Retrieved on Nov. 27, 2015.

Chionglo, J. F. (2015) "A Reply to 'When do deadlocks occur?' at Computer Science Stack Exchange.
> 0 votes

---
Tags: operating-systems, concurrency, deadlocks
---


# Question
Title: Meaning of $\stackrel{*}{\rightarrow}$ production rule?
I've seen the production rule $\stackrel{\*}{\rightarrow}$ in some papers concerning regular languages.

What's the meaning of $\stackrel{\*}{\rightarrow}$ production rule?

# Answer
It's either the transitive closure or reflexive-transitive closure of $\rightarrow$. That is, $A\rightarrow B$ means that you get from $A$ to $B$ in exactly one step; $A\rightarrow^\*B$ means either you get to $B$ in one or more steps (transitive closure) or in zero or more steps (reflexive-transitive closure).
> 5 votes

---
Tags: formal-languages, regular-languages, notation
---


# Question
Title: What does it mean for a problem to be both NP hard and coNP hard
I have a faint notion of what NP hard is (that a problem is legit difficult 3 SAT for example).

I have forgotten what coNP hard, and Wikipedia tells me that the complement of coNP hard is NP hard...not really helping there

Can someone please clarify for me on an intuitive level what does it mean for a problem to be coNP hard? Further, what does it mean for a problem to be both NP hard and coNP hard? What is a problem that illustrate this concept?

Thank you!

# Answer
> 6 votes
A language $L$ is *NP-hard* if for every language $R$ in NP there exists a function $f$ computable in polynomial time such that for all $x$, $x \in R$ iff $f(x) \in L$.

A language $L$ is *coNP-hard* if for every language $R$ in coNP there exists a function $f$ computable in polynomial time such that for all $x$, $x \in R$ iff $f(x) \in L$.

If a language is both NP-hard and coNP-hard then its exact complexity lies above both NP and coNP. Indeed, it is conjectured that NP$\neq$coNP, and this implies that a problem which is both NP-hard and coNP-hard belongs to neither NP nor coNP.

Problems which are both NP-hard and coNP-hard do exist. For example, any PSPACE-complete problem is both NP-hard and coNP-hard.

# Answer
> 6 votes
When a problem is NP-complete, it is hard to find out whether the answer is yes or no but if the answer is yes, there are short witnesses that are easy to check (but not easy to find).

For example SAT is NP-complete so if you have a Boolean formula it is hard to say whether it is satisfiable. However, if I tell you that your formula if satisfiable for example by setting $x\_1,x\_2,x\_7,x\_8$ to true and the other variables to false, you can check that easily. On the other hand, if I tell you that the formula is not satisfiable, I do not have an easy way of convicing you, short of going through all valuations with you.

Now look at VALIDITY of Boolean formulae, another decision problem. The situation is reversed. If your formula is not valid, I'll convince you easily with a witnessing valuation. While if it is valid, I do not have short witnesses that will convince you. BTW, did I mention that VALIDITY is coNP-complete?

So NP-complete problems have short witnesses for "yes" answers while coNP-complete problems have short witnesses for "no" answers. As they say "the two are the same thing modulo swapping of yes and no so that they are in fact just the opposite".

If we forget about completeness, NP-hard problems *may* have short easy witnesses for "yes" answers but (unless P=NP) do not have such short easy witnesses for "no" answers. With coNP-hard problems, the "yes" answers do not have short easy witnesses (unless ..)

# Answer
> 3 votes
When wikipedia says the complement, that's literally what it means:

A problem $L$ is in NP if there's a non-deterministic Turing Machine $M$ that, for every word $w \in L$, that accepts $w$ in polynomial time.

A problem $L$ is in co-NP if there's a non-deterministic TM that rejects all words $x \not \in L$ in polynomial time.

The question is, if you have the "guessing" that a non-deterministic TM gives, does it help you find yes solutions fast, or no-solutions fast?

For example, there are a bunch of $coNP$ hard problems asking, for some sets $S, T$, is $S \subseteq T$. If have an element $x \in S, x \not \in T$, then we can verify in polynomial time that the subset relation does not hold.

There is a problem in NP for every problem in coNP, and vice versa. For example, the SAT problem asks "does there exist a boolean assignment which makes this formula evaluate to True?". The complement problem, which is in coNP, asks, "do all boolean assignments make this formula evaluate to False?"

Being coNP hard just means that you can reduce in polynomial time from every other problem in coNP. So if a problem is NP-hard, its complement is coNP hard.

The reason this is interesting is, we don't actually know if $NP = coNP$. The general hypothesis is that it does not. If we assume $NP \neq coNP$, then you can prove that a problem is not NP-complete (or coNP complete) by showing that it is in both $NP$ and $coNP$.

---
Tags: complexity-theory, intuition
---


# Question
Title: How to balance parentheses/brackets in a string with minimum cost?
Given a word composed of opening and closing parentheses and brackets, we can do two operations:

* Rotate a parentheses or bracket. That is, you can replace ( for ), ) for (, \[ for \] and \] for \[. This operation has cost 1
* Replace a parentheses for a bracked and viceversa without changing its orientation. That is, change ( for \[, ) for \], \[ for ( and \] for ). This operation has cost 2.

Which is the minimum cost to balance the given word properly? For example, given \]( we can achieve \[\] by rotating twice and replacing once, with a total cost of 4

# Answer
> 0 votes
Two possible recursive approaches.

* The string $(w$ is balanced iff $w$ is of the form $u)v$ where each of $u$ and $v$ are balanced (but either of them may be empty).
* The (nonempty) string $w$ is balanced iff it is of the form $(u)$ where $u$ is balanced, or it is of the form $uv$ where each of $u$ and $v$ are balanced (and nonempty).

---
Tags: algorithms, dynamic-programming
---


# Question
Title: Why are multi-threading programs more prone to errors?
Why are multi-threading programs more prone to errors than single threaded programs ? or why is multi-threading programming one of the areas where developers are (more) prone to errors? Is this in general or is it valid only for scenarios where there are shared resources being used by multiple threads ? Are the difficulties to detect errors or simulate bugs in multi-threaded programs just related to inexperience or immature tool support, or are they fundamentally more difficult than the same tasks for single threaded programs ?

# Answer
> 7 votes
# Overview

Multi-threaded programs are more prone to errors than single-threaded programs because of the problem of concurrency bugs. Concurrency is hard for most developers to reason about, which causes many bugs in multi-threaded programs; this issue normally doesn't arise in single-threaded programs, because single-threaded programs typically have no concurrency.

# Mutable shared state, and plan interference

The core problem is due to the combination of multi-threaded programming plus mutable shared state. If there was no shared state, or if all shared state was immutable, then you wouldn't have to worry about concurrency bugs. But when you have mutable shared state, then the programmer has to start thinking about all possible interleavings of the thread A's accesses to the shared state with thread B's accesses to the shared state. There can be exponentially many possible interleavings that the programmer needs to reason about, if they want to avoid concurrency bugs, and no surprise, that's non-trivial.

Mutable shared state introduces the possibility of data races and other kinds of concurrency bugs. These can be tricky to reason about.

Multi-threaded programming makes it easy to have *plan interference* problems. Programmers tend to think in a single-threaded way: they think about a single sequential path of execution. When they're writing the code for a particular function/method/module, they build in their head a "plan" of the operations/actions they want to have happen, typically based on a single-threaded mental model (e.g., based on the implicit assumption that nothing else will interrupt them in the middle of this sequence of actions or concurrently modify their internal state). However, when you have multiple threads with mutable shared state, they can cause unexpected interference while the code is in the middle of execution (changing something out from under the code while it is in the process of executing the programmer's plan).

For example, here is one classic example of plan interference. Imagine you have a publish-subscribe data structure that lets clients register themselves as observers, and delivers events to all registered observers. Imagine its code is in the middle of delivering an event to the observers, one by one, and the code of one of the observers happens to mutate the underlying state; this mutation might cause the notifications to the other observers to happen in the wrong order, or to expose an inconsistent state to them.

# Further reading

For a more general description of the plan interference problem and more general discussion of why multi-threaded programming is more error-prone, I recommend the following papers:

# Candidate solutions

Multiple candidate solutions have been proposed:

* One possible solution is to avoid using threads, and program in a sequential single-threaded way. This is how Javascript works in browsers, for instance.
* Another is to use threads but avoid all mutable shared state. For example, Erlang.
* A third is to use message-passing rather than mutable shared state for interaction between the threads. One can build systems based on the actor model. For example, E.
* A fourth is to use threads with mutable shared state, but just be really careful. You can have systematic ways of locking shared data and preventing data races and avoiding plan interference and so on.

See also https://cs.stackexchange.com/a/27803/755 for similar ruminations (I borrowed some text from there).

# Answer
> 1 votes
there is some long scientific study on this subject. there are different ways to answer this but one standout aspect of multithreaded programming is how much it has evolved over many decades. decades ago, it was less understood and even more of a research topic, and there were not standardized ways of accomplishing multithreading. in multithreading, there are many ways to do nearly the same thing and some ways are more complex or error-prone than others. it has taken a long time and major research ingenuity to identify/ sort out these patterns.

early computer systems were not multithreaded and even major commercial operating systems such as windows OS/ Macintosh a few decades ago (early 1990s) had unsophisticated/ more primitive multithreading approaches such as nonpreemptive multitasking where a single "misbehaving" program could interfere with other programs.

multithreaded programming predates design patterns study. design patterns have had a major influence on multithreaded programming theory.

so the idea that multithreading programming is inherently bug prone has somewhat lessened over time. it is to some degree inherently tricky but if the developer is trained well in theory/ standardized design patterns and uses them instead of avoiding them, the bug prone aspects of multithreading can be significantly mitigated. (this could even be seen as one of the major "success stories" in computer science in general.)

as R points out in comments, multithreading is inherently typically nondeterministic and not "repeatable" unless specifically designed that way. the exact same code may run in different thread orders depending on very subtle factors such as current CPU load etc. and this can complicate troubleshooting.

a major design pattern now widely available in many languages (not always under the same name) is known as Communicating Sequential Processes where thread safety is provable/ verifiable and not hard to guarantee if the patterns are followed. it has strong similarities to the unix pipeline concept.

see eg

---
Tags: concurrency, threads
---


# Question
Title: How does Hassin's algorithm for the Restricted Shortest Path work?
I'm studying the Approximation For Restricted Shortest Path Problem paper and don't understand what he is doing. In particular, I wonder why it is important that one computes upper and lower bounds $UB$ and $LB$ on $OPT$, so that their ratio is below some constant.

The problem is to find the least-cost path from nodes $1$ to $n$ where the cumulative delay (each edge has a delay/transit time in addition to cost) is no more than some $T$.

For the restricted shortest path problem, the exact solution can be found in pseudopolynomial time $\mathcal{O}(|E|OPT)$like this.

> Let $g\_j(c)$ be the time of the quickest path form node $1$ to node $j$ with cumulative cost $\le c$. \begin{align\*} g\_1(c) & = 0, & c = 0,\ldots,OPT, \\ g\_j(0) & = \infty, & j = 2,\ldots,n, \\ g\_j(c) & = \min\left\\{g\_j(c-1), \min\_{k \mid c\_{kj} \le c}\left\\{g\_k(c-c\_{kj}) + t\_{kj}\right\\}\right\\}, & j = 2,\ldots,n; ~ c= 1,\ldots,OPT \end{align\*}

So Hassin constructs a $TEST(k)$ procedure which says $YES$ if $OPT \ge k$ and $NO$ if $OPT \< k(1 + \epsilon)$

He then proceeds to pick initial bounds $UB$ and $LB$ and uses the $TEST$ to refine them until $\frac{UB}{LB} = 2$. He then computes the final solution with the exact algorithm, but where each edge cost $c\_{ij }$ is scaled as $\hat{c}\_{ij} = \lfloor\frac{c\_{ij} (n-1)}{LB\epsilon}\rfloor$. So what I would like to know is how this application of the exact algorithm is actually polynomial. I suppose that the optimal solution in this modified graph is somehow bounded, but I do not see where the ratio of $2$ comes into play.

# Answer
> 1 votes
I have one theory now, which is that the final application of the exact algorithm on the scaled costs has complexity $\mathcal{O}\left(|E| OPT\frac{(n-1)}{LB\epsilon}\right) \subseteq \mathcal{O}(|E| 2LB\frac{(n-1)}{LB\epsilon})=\mathcal{O}(|E| 2\frac{(n-1)}{\epsilon})=\mathcal{O}\left(|E|\frac{n-1}{\epsilon}\right)$ which is then polynomial in $n \le \sqrt{|E|}$ and $\epsilon$. Can anybody confirm this?

---
Tags: graphs, dynamic-programming, shortest-path, approximation
---


# Question
Title: What is the fastest way to a Publish/Subscribe pattern?
I am running in a conceptual problem in my development which I previously also encountered in the Drupal CMS and was wondering what would be the best solution to circumvent the problem.

Drupal, and my own Snap Websites software, make use of a publish / subscribe pattern where one can write functions that automatically get called whenever a certain event happens. This can be shown in the following process (note that neither are using threads in those specific processes, it runs within one single main thread in one single main process--although Snap! supports backends—separate processes, I have no concerns with those at this point):

```
+----+    +----+    +----+    +----+      +----+
| P1 |--->| P2 |--->| P3 |--->| P4 |-...->| Pn |
+----+    +----+    +----+    +----+      +----+
            |                   |
            |                   | p4 signal  +------+    +------+      +------+
            |                   +----------->| O1/4 |--->| O2/4 |-...->| On/4 |
            |                                +------+    +------+      +------+
            |
            | p2 signal  +------+    +------+      +------+
            +----------->| O1/2 |--->| O2/2 |-...->| On/2 |
                         +------+    +------+      +------+

```

Shown here we see that process P2 emits a signal (p2 signal) and that generates functions of observers O12, followed by O22, etc. up to On2 to be called. The exact same thing happens in process P4.

In most cases that works just fine. However, once in a while, a change made by one of the observers is required by the next observer. In other words, the order O12 then O22 is important. However, if the end user has the possibility to switch the two observers around, then the process becomes O22 then O12 which breaks the proper sequence and thus something will not happen.

The Drupal awkward solution is to use a weight to sort their modules in a given order. This is an issue because that forces all observers of that module to happen in that order when some of the events may need to happen before and others after. Drupal modules with equal weights are sorted alphabetically, which at least provides some form of consistency.

It seems to me that the proper way would be to generate signal p2 again if one of the observers made a change that warrant the signal p2 to be re-run. There are two problems in such an implementation:

1. We have to be careful to not generate an infinite loop, so an observer should not re-generate the signal if what it needs to do was already done in a previous call \[this can be complicated though\]; and
2. We are probably going to re-execute the code of many observers for nothing.

Called again:

```
+----+    +----+    +----+      +----+
| P1 |--->| P2 |--->| P3 |-...->| Pn |
+----+    +----+    +----+      +----+
            |
            |
            |<--------------------------+
            |                           | p2 signal after P2-like change
            |                           |
            | p2 signal  +------+    +------+      +------+
            +----------->| O1/2 |--->| O2/2 |-...->| On/2 |
                         +------+    +------+      +------+

```

The other way would be for each observer to tell us whether they should run before or after certain other observers. This means observers have knowledge that they probably should not have, although I am not so sure that this is really a bad thing.

A concrete example of the problem in my Snap! Websites environment:

\[Client Side\]

1. User uploads a PDF file
2. Client process (i.e. browser) sends PDF to server
3. Server transforms PDF to a preview image
4. Client checks to see whether the PDF preview is ready

In step 3 the server process is something like this:

\[Server Side--i.e. front end server\]

1. The Editor plugin receives POST event with the PDF file in it
2. The Editor plugin calls a Content function to save the PDF in the database
3. A Page plugin observer is called as the Content plugin sends a "created content" signal
4. The Page plugin observer links the PDF file to a script that will be used to generate the PDF preview image (this is a Magick++ script, you can define different sizes, quality, flipping, etc.)
5. The Images plugin also has an observer on the "created content" signal, that observer detects the link created by the Page plugin observer and mark that PDF for future processing by our Image plugin backend
6. The server process returns to the client (i.e. this was very fast, a few ms)

In the Images plugin backend process (a completely separate process which can even run on a computer by itself):

\[Backend Side--i.e. server possibly not accessible from the front end\]

1. The Images plugin backend process wakes up
2. The Images plugin backend checks for new data to process and finds the PDF
3. The Images plugin backend runs the script attached to the PDF document
4. The Images plugin backend saves the preview of the PDF along its other file in the database, ready to be retrieved by the client (step 4 of the first process.)

As we can see in the Server process, step (5) fails if step (4) does not happen before it, which in the Snap Websites environment, at this point, means the Page plugin must be loaded before the Images plugin.

# Answer
> 6 votes
Since you are asking on CS.SE rather than StackOverflow, I presume you are looking for a principled look at the fundamental underlying problem and principled solutions to the general problem, from a scientific/conceptual perspective (as opposed to a "quick hack" or a engineering solution that'll work for your specific situation). So, that's what I'll try to provide.

## The problem

What you are describing is an instance of the *plan interference* problem.

Let me summarize the problem in abstract terms. You are in the middle of delivering an event to the observers, one by one, and the code of one of the observers happens to mutate the underlying state; this mutation might cause the notifications to the other observers to happen in the wrong order, or to expose an inconsistent state to them.

For a more general description of the plan interference problem, I recommend the following papers:

## Some candidate solutions

One possible solution, proposed in the first paper above, is to stop using threads with mutable shared state as your form of concurrency. Instead, look at systems like Erlang and others that are more event-based and use alternative models of concurrency.

Another possible solution, proposed in the second paper above, is to stop using threads with mutable shared state as your form of concurrency. Instead, look at systems that are inspired by actors. These systems treat invoking a method on an object $O$ as sending a message to the object $O$, and instead of using a stack discipline, they use a message queue. This ensures that messages are delivered in an order that are consistent with the causality, and avoids causing plan interference. For instance, if you're in the middle of delivering an event to a bunch of observers, and the third observer triggers a state-changing method call $c$, then these systems would queue up $c$ and not deliver/invoke it until all of the observers have been informed. This avoids unexpected violations of atomicity and avoids many kinds of plan interference bugs. See the second paper for details.

A third alternative solution is to continue using threads with mutable shared state as your form of concurrency, and just *be really careful*. You could make yourself aware of the common kinds of plan interference hazards, and write your code so you won't shoot yourself in the foot in this way. For instance, the state-holding object could make itself responsible for queuing up notifications about state changes, to ensure that notifications happen in a consistent order. It could also establish a contract that forbids observers from making mutations to itself (so there is no mutual recursion where a change to the state of object $x$ triggers a notification to observer $O\_i$ which in turn mutates the state of object $x$ some more). You could structure your code so that the order in which observers are invoked should never matter. There are all sorts of ways you could structure your code to try to avoid these hazards from ever affecting you.

Obviously, this last approach is very challenging, because it is difficult to reason about all the things that could happen in such a system. It's easy to screw something up. But hey, concurrency is really hard to think about. If you write your code using shared-state concurrency, don't be surprised if it makes your code harder to reason about.

Plan interference can occur even in single-threaded programs, so this problem is not exclusive to multi-threading. (I mention multi-threading only because it is the most common cause of plan interference problems.) The second paper above does propose solutions to plan interference that will apply even to single-threaded programs.

# Answer
> -1 votes
a different angle: your problem looks similar to me to a common concept in CS, lets use a simple/ common/ widespread example of the problem of updating cells in a spreadsheet. imagine each cell in the spreadsheet depending on other cells. the spreadsheet has to recalculate in an efficient way if one of the cells changes, eg not repeat calculations as the overall spreadsheet "fluctuates". if you have cell A depend on cell B and cell B depend on cell A, you could have an infinite loop. this same situation arises in the "Publish/ Subscribe" pattern in CS also called "observers" or "listeners".

the natural way to model/ analyze this is an (acyclic) directed graph, also called circuits in computer science. if you have any cycles you know you have an infinite loop.

the propagation of signals through the network then is like current or information moving through a circuit.

there is also some analogy to a dependency graph in software compilation where there is a tree of dependencies where code depends on APIs etc.

this works for a deterministic situation in which observers always update based on new information, where cycles will imply an infinite loop. however you seem to indicate the possibility of some "nondeterminism". an element may or may not update its information based on the new information.

in this case the problem of determining ahead of time whether the system will eventually stop calculating from "cascades of updates" is probably undecidable in general! (unless you somehow limit the calculation logic...)

---
Tags: concurrency, software-engineering, threads
---


# Question
Title: Using natural deduction, show that: ∀x.(P (x) → Q(x)), ∃x.P (x) ⊢N ∃x.Q(x)
1. How I would show: **∀x.(P (x) → Q(x)), ∃x.P (x) ⊢N ∃x.Q(x)** using Natural Deduction?
2. Would I not need to know what P(x) and Q(x) are to prove soundness and completeness?

# Answer
> 4 votes
We would like to prove $(\forall x . P(x) \to Q(x)), (\exists y . P(y)) \vdash \exists z . Q(z)$.

Let us first do it in plain language, but still in natural deduction. We have hypotheses

1. $(\forall x . P(x) \to Q(x))$
2. $\exists y . P(y)$

We use hypothesis 2: there is $a$ such that $P(a)$. We use hypothesis 1 applied to the case $x := a$ to obtain:

3. $P(a) \to Q(a)$.

We already know that $P(a)$, therefore we can use 3 to get $Q(a)$. We therefore conclude that $\exists z . Q(z)$. QED.

I am not going to draw boxes because you can get them on the web:

* go to ProofWeb and in the section called "Proof assistants on the web" login as guest and select the Coq proof assistant.
* under the "Display menu option select "Fitch style box proofs" or "Gentzen-style tree proofs"
* type the following code into the left-hand window:

```
Parameter A : Set.
Parameter P : A -> Prop.
Parameter Q : A -> Prop.

Lemma foo: (forall x, P(x) -> Q(x)) -> (exists y, P(y)) -> exists z, Q(z).
Proof.
  intros H1 H2.
  destruct H2 as [a H2'].
  exists a.
  apply (H1 a).
  exact H2'.
Qed.

```
* Now move down line by line with the "down" arrow in the upper-left corner. Watch the proof unfold in the lower-right text area.

# Answer
> 4 votes
> Would I not need to know what $P(x)$ and $Q(x)$ are to prove soundness and completeness?

No. The phrase "formal logic" isn't the opposite of "casual logic": rather, it means, logic based on the form (i.e., structure) of propositions, not on their interpretation as statements about the world. In formal logic, the statements "Socrates is a man; all men are mortal; therefore, Socrates is mortal" has exactly the same form as "sploon is a fneep; every fneep is blunfish; therefore, sploon is blunfish", and "$\big(P(a) \land \forall x\\,(P(x)\rightarrow Q(x))\big)\rightarrow Q(a)$". The logical truth is independent of any meaning you might want to ascribe to $P$ and $Q$.

Also, soundness and completeness are properties of proof systems, not individual formulae so your question seems to contain a category error.

---
Tags: logic
---


title: Time complexity - least upper bound

text:
# Question
Title: Time complexity - least upper bound
I know that Big $O$ notation is used to describe the upper bound of running time of an algorithm, if we consider time complexity of that algorithm. However, I'm not sure why the following is **not** stated everytime anyone attempts to explain time complexity or Big $O$ - the fact we're looking for the least upper bound of the running time.

Correct me if I'm wrong, but $O(n!)$ is known to be the highest complexity - much worse than exponential. If I have an algorithm whose running time is $O(n)$, then it is also $O(n^2)$, $O(n^3)$, $O(2^n)$, and $O(n!)$, because they are all upper bounds of its running time (I know that, because it's $O(n)$).

So is it possible to find the least upper bound of the running time? If I read an algorithm has complexity $O(2^n)$, does it mean it has been proven this is the least upper bound? Or is it just the smallest upper bound that has been found **so far**?

# Answer
> 1 votes
If you want to state that $O(f(n))$ is the best bound on the complexity that you can get, then you can use big Theta instead: $\Theta(f(n))$ stands for a function – in this case worst-case time complexity – that is asymptotically equal to $f(n)$ up to constants. That is, if the worst-case time complexity $T(n)$ satisfies $cf(n) \leq T(n) \leq Cf(n)$ for some $0\<c\leq C$, then you can state that the (worst-case) time complexity of the algorithm is $\Theta(f(n))$. This implies both the upper bound $O(f(n))$ and the matching lower bound $\Omega(f(n))$, showing that the upper bound is best possible.

---
Tags: complexity-theory, time-complexity
---


title: Upper bound of algorithm with flooring

text:
# Question
Title: Upper bound of algorithm with flooring
Would much appreciate someone explaining how they managed to get to the upper bound of this algorithm. $$T(n) = 2T(\lfloor \sqrt n\rfloor) + ln (n)$$ $$T(1) = 0$$ Solution is given as: $$T(n) = O(logn\*log(log(n)))$$

# Answer
If a number is of the form $n = 2^{2^k}$ then you never encounter the floor as you open up the recursion, and then there is no problem. If you're interested in a general upper bound, you can prove by induction that $T(n)$ is monotone in $n$: if $n \leq m$ then $T(n) \leq T(m)$. Now given $n$, find some $m \leq n^2$ which is of the form $2^{2^k}$, and then $$ T(n) \leq T(m) = O(\log m \log\log m) = O(\log n \log\log n). $$
> 1 votes

---
Tags: algorithms, algorithm-analysis, recursion
---


title: Nullable nonterminals and recursion

text:
# Question
Title: Nullable nonterminals and recursion
I have two questions regarding nullable nonterminals in a grammar. Often a simple algorithm is described to find nullable nonterminals:

> 1. Basis: if $A \rightarrow \epsilon$ is a production, $A$ is nullable.
> 2. Induction: if $A \rightarrow X\_1X\_2\ldots X\_n$ is a production, and $X\_1, X\_2, \ldots, X\_n$ are all nullable, then $A$ is nullable.

Intuitively, this algorithm seems correct. But I don't see how it could properly show $B$ to be nullable in the following grammar:

$$A \rightarrow a$$ $$A \rightarrow \epsilon$$ $$B \rightarrow B A$$

How does the algorithm deal with these recursive productions that are nullable? If not, what changes must be made to make it correct?

---

My second question is whether the following grammar is nullable, or whether it's even a valid context-free grammar at all.

$$S \rightarrow S$$

# Answer
> 4 votes
A nonterminal $X$ is *nullable* if there is some derivation $X \to^\* \epsilon$. It is clear that all non-terminals found by your algorithm are nullable (you can prove this by induction). On the other hand, if $X$ is nullable then take a derivation tree for the derivation, and prove by induction on the depth that all non-terminals on the way are recognized as nullable by this algorithm. This is why the algorithm is correct.

In your first example, $B$ is not nullable. In fact, you can't generate *any* string from $B$. The same is the case for your second example $S\to S$, where again the grammar generates no strings.

---
Tags: context-free, formal-grammars
---


# Question
Title: How to write Context-free Grammar for this language?
I am trying to teach myself how to write Context-free Grammar for different languages. I have an example language I am trying to work out and this is the answer I came up with, does it make sense?

the language is (i used an image because i don't know how to write out the powers on a mac):

This is my answer:

```
S --> rSjZr | Z
Z --> oo

```

I've been trying to learn it by reading other people's CFG's, however I am still unsure of how it works, my thinking is that, if `j` and `k` are 0 then `r` becomes 0 as well because 2\*0 would return 0 and I therefore end up with `oo`. However, I am unsure about the first part it seems like it could make sense and at the same time it doesn't could somebody please explain to me how they would write a context-free grammar for the language and if my answer makes sense?

Thanks

# Answer
> 0 votes
A couple of things:

Sometimes it helps to simplify the description of your grammar. Instead of $\\{r^{2j+k}j^ko^2r^j \mid j,k \geq 0 \\}$, you can write this: $\\{r^{2j}r^kj^koor^j \mid j,k \geq 0\\}$. It is still the same grammar, but you can easier see what you're doing.  ~~For example, something here stands out: $\\{r^{2j}\mathbf{r^k}\mathbf{j^k}oo\mathbf{r^k} \mid j,k \geq 0\\}$~~

Next: Sanity-checking. See if what you're trying to achieve conflicts with any known rules. Can this language be produced by a context-free grammar? Or is this language not context-free? ~~Consider that $\\{ a^kb^kc^k \mid k \geq 0\\}$ is a classical example for non-context-free grammars (It is context sensitive).~~

If the language is not context-free, we can stop trying to find a context-free grammar for it. Attempts will be (hopefully) futile.

Unfortunately, I can't provide you with a simple way of constructing grammars for context-free languages. Maybe (probably) some other (far more experienced and knowledgeable) members here might be able to do so. What worked for my (short) stint in TCS, practice helped. I started with simple examples, and increased their complexity. Then you learn to recognize some patterns in languages and solve them for example by splitting the language into multiple, smaller and simpler languages which you already know how to solve.

Lets try to apply that to this case: $\\{r^{2j}r^kz^koor^j \mid j,k\geq0\\}$ We can see that that is essentially $\\{r^{2j}$ \[something else\] $r^j \mid j\geq0\\}$. That is easy to produce:

$S \rightarrow rr X r | X$, where $X$ will produce the \[something else\]. That something else is of course $r^kz^koo \mid k\geq0$, which is also easy to produce:

$X \rightarrow Y oo | oo$ and

$Y \rightarrow rYz$

Ultimately, the key behind this construction was simplifying the language, and then recognize that the language is a nested variation of $\\{a^k\ b\ a^k\\}$ and $\\{a^k\ b^k\ a\\}$, which both are trivial languages to produce.

---
Tags: formal-languages, context-free, formal-grammars
---


title: Comparing asymptotic notations

text:
# Question
Title: Comparing asymptotic notations
I have a problem P that is said to be O(n^7) in the worst case. I'm asked to agree or not if it is solvable in O(n^9) time. And also I'm asked to agree or not if P cannot be solved faster than Ω(n^7) in the worst case.

My answer for the first question is that if P is bounded by O(n^7) it is also solvable in O(n^9).

And for the second question: Ω(n^7) means that the running time cannot be less than n^7, but we already know that P is bounded by O(n^7) in the worst case and it is not proven that it can't be solved faster, so I think this statement is false.

So my questions are: how do I prove the answer for the first question and how do I express my second answer in terms of functions? I've seen a lot of info about asymptotic notations, but I couldn't find any info that could enlighten me how to answer the questions I am asked.

Thanks.

# Answer
> 2 votes
If P is solvable in $O(n^7)$, that means that P is solvable in $C \cdot n^7$ time, for some constant $C\>0$ and large enough $n$. Since $C \cdot n^7 \< C \cdot n^9$ for large enough $n$, that implies that P is solvable in $O(n^9)$.

P is bounded by O($n^7$) in the worst case, but it does not imply that in the best case cannot run in constant time, for instance. Thus, P is not greater than $C \cdot n^7$ for large enough $n$, so it is not $\Omega(n^7)$.

---
Tags: asymptotics, landau-notation
---


# Question
Title: What does it mean when a time complexity has another time complexity within it?
Sometimes, when reading about algorithms or other theoretical topics, I see time complexities that include other time complexities within the expression.

For instance, "the best fixed-parameter tractable algorithm for the vertex cover problem has a time complexity of $O(1.2738^{k} \cdot n^{O(1)})$."

What does this $O(1)$ expression mean? Can I just replace it with any constant and the time complexity will still hold?

# Answer
> 3 votes
This is somewhat informal, and to figure out what it means, just parse it inside-out:

* $f(n)$ is $O(1)$ means, as usual "$\exists c, n\_0: f(n) \leq c$ whenever $n \geq n\_0$".
* $f(n)$ is $n^{O(1)}$ is meant to mean "$f(n)$ is of the form $n^{g(n)}$, where $g(n)$ is $O(1)$".

Formally put, $\exists c, n\_0: f(n) \leq n^c$ whenever $n \geq n\_0$.
* $f(n)$ is $O(2^k \cdot n^{O(1)})$ means "$\exists c, n\_0: f(n) \leq c\cdot 2^k\cdot n^{g(n)}$, where $g(n)$ is $O(1)$".

Formally put, $\exists c\_1, c\_2, n\_0: f(n) \leq c\_1 \cdot 2^k\cdot n^{c\_2}$ whenever $n \> n\_0$.

Note that you cannot simply replace the internal $O(1)$ with any fixed constant. You know that a suitable constant does exist, but its value is left unspecified.

---
Tags: algorithms, complexity-theory, time-complexity
---