# Question
Title: Maintain statistics over a sliding window (robust & efficient)
I am looking for an algorithms to maintain several statistics over a sliding window. The setup is as follows: There is a datastream consisting of (real value,timestamp) tuples. The values for the last x seconds are stored. In each iteration at least one new tuple arrives and between zero and more values are retired. Now I want to maintain mean and variance without recomputing everything from scratch. There are methods if values are never retired, e.g. Welford's method. But what if values are retired?

The second problem I am facing is, how to compute covariance between two sliding windows in a similar fashion?

Are you aware of a solution or references?

# Answer
To compute the mean of all the values in your window, separately compute (a) the sum of all the values in the window, and (b) a count of the number of values in the window.

To keep track of the sum of all the values in the sliding window, each time you receive a new value, add it to the sum. Each time a value leaves the window, subtract it from the sum. Now you'll always have a sum of the values in the window.

To keep track of the number of values in the window, each time you receive a new value, increment the counter. Each time a value leaves the window, decrement the counter.

Finally, the mean is the sum divided by the count.

To keep track of the variance, you need the count, the sum of the values, and the sum of the squares of the values. You can keep track of the sum of the squares of the values in the window in the same way (when a new value arrives, add its square to the running sum; when a value leaves, subtract its square). These three values are enough to let you compute the variance of the values in the sliding window.

Note that when using the sum of squares method to compute the variance, you will need to compute the three intermediate values to enough digits of precision. If you don't have enough digits of precision for those intermediate values, then you get a very inaccurate estimate. This is the robustness problem that is mentioned in the blog post you link to and that is addressed by Welford's method. However, there is another pragmatic way to address it that will work for most practical settings: just compute those three intermediate values to more digits of precision.

For the covariance between $x\_1,\dots,x\_n$ and $y\_1,\dots,y\_n$, you need to know the sum of the values $x\_i$, $x\_i^2$, $y\_i^2$, $x\_i y\_i$, and the count $n$. So, it's basically the same principle as above, but now there are five intermediate values you need to maintain, instead of just three.
> 2 votes

# Answer
Usually, an exact solution is impossible (unless you keep the entire window in memory), however it is possible to approximate the output as a function of the amount of memory you are allowed to have. A good starting point would be

They show how to maintain the sum of a positive-value data stream (then, computing the average is just dividing in the window's size). The mainly assume a fixed window size (i.e., at each time step a new item arrives and one old item expires), however they also discuss the model you are interested in, where each element has a time-stamp, and several items may expire at the same time. Check if *Exponential Histogram* (or their extension, *smooth histograms*) may give you what you need.

Another good source of information for data streams in general would be the survey
> 2 votes

---
Tags: algorithms, statistics
---


title: Seemingly non sequitur in proof

text:
# Question
Title: Seemingly non sequitur in proof
I'm trying to understand a small proof in an article about computing lumpability on Markov chains. There is a small detail that I cannot understand, i.e. I don't think it follows from the argument.

The article is *Simple $O(m\log{n})$ Time Markov Lumping* written by Valmari & Franceschinis.

Given a weighted graph they define the notion of *compatible partition* of its nodes. Which is a partition $P$ such that for all $B, B' \in P$ and all $s\_1, s\_2 \in B$ we have that:

$$ W(s\_1, B') = W(s\_2, B') $$

They describe an algorithm to compute the coarsest refinement of an initial partition that is compatible (the coarsest *croip*= compatible refinement of initial partition). The algorithm follows the idea of Paige and Tarjan to compute bisimulation: we take a block $S$ from the partition as a *splitter* and check whether some other block $B$ breaks the condition above, and if it does we split $B$ into $B\_1, \ldots, B\_k$ such that the $B\_i$ satisfy the condition above when taking $B' = S$.

How exactly these checks are performed shouldn't be essential for the correctness of the algorithm. In the proof of correctness they prove the following lemma:

> **Lemma 2.** Let $d\_1, d\_2$ be nodes of the graph. If the algorithm ever puts $d\_1$ and $d\_2$ into different blocks, then there is no croip where $d\_1$ and $d\_2$ are in the same block.

The proof for when the algorithm separates $d\_1$ and $d\_2$ during its execution is the following:

> **Proof.** We show that it is an invariant property of the main loop of the algorithm (that is, always valid on line 2*) that if two states are in different blocks of the algorithm, then they are in different blocks in every croip.
>
> If $d\_1$ and $d\_2$ are in different blocks initially, then they are in different blocks in $I$ and thus in every croip.
>
> The case remains where lines 14 to 20 separate $d\_1$ and $d\_2$ to different blocks.
>
> This happens only if $W(d\_1, S) \neq W(d\_2, S)$. Let $P$ be an arbitrary croip. **It follows from the invariant that each block of $P$ is either disjoint with $S$ or a subset of $S$**, because otherwise the algorithm would have separated two states that belong to the same block of a croip. Therefore, there are blocks $S\_1 , \ldots, S\_k$ in $P$ such that $S\_1 \cup \cdots \cup S\_k = S$. The fact $W(d\_1, S) \neq W(d\_2, S)$ implies that there is $1 \leq i \leq k$ such that $W(d\_1 , S\_i) \neq W(d\_2, S\_i )$. So $d\_1$ and $d\_2$ belong to different blocks in $P$.

I have a problem understanding the text in bold. To me: it's simply false. They justify it saying *otherwise the algorithm would have separated two states that belong to the same block of a croip.*

However:

* we still haven't proved the algorithm correct, so I don't really see how the algorithm doing something should imply anything at this point
* I don't get if the two states separated are $d\_1$ and $d\_2$ or if they are referencing other states

So, I see this as a non sequitur, which would invalidate the proof of this lemma and thus the whole correctness proof of the algorithm.

Given that the algorithm was developed to fix a wrong algorithm published previously from other authors, I believe Valmari and Franceschinis were very careful in the proofs, so I'm probably missing something trivial. Can anybody point out what I'm missing?

---

* The algorithm is simply a main loop that chooses a new splitter $S$ for each iteration and splits all the blocks in the partition and goes on.

# Answer
> 2 votes
The invariant states that if at some point of the algorithm, $d\_1,d\_2$ are in different blocks, then in every croip, $d\_1,d\_2$ are in different blocks. The contrapositive of the invariant states that if $d\_1,d\_2$ are in the same block of some croip, then they are always in the same block during the running of the algorithm.

Now consider a block $S$ of your algorithm and a block $T$ of an arbitrary croip. We want to show that either $T \subseteq S$ or $T \cap S = \emptyset$. If not, then take some $d\_1 \in T \setminus S$ and some $d\_2 \in T \cap S$. Since $d\_1,d\_2 \in T$, they are in the same block of some croip, and so the contrapositive of the invariant states that they are always in the same block during the running of the algorithm. But $d\_1 \notin S$ while $d\_2 \in S$, and we reach a contradiction. We conclude that either $T \subseteq S$ or $T \cap S = \emptyset$.

---
Tags: correctness-proof, weighted-graphs, markov-chains
---


# Question
Title: Are there any theorems/formulas that apply to the height of comparison trees?
I have been drawing some binary comparison trees, which correspond to compares made to sort an array, and I was wondering if there is any formula to determine the height of a comparison tree for an array of N values, in Sedgewick's algorithms 4th ed. book for N = 3, the height of a comparison tree is 3.

He draws his comparison trees in such a way that all the internal nodes and the root represent the comparisons, for example (i:j) means compare a\[i\] to a\[j\], if a\[i\] \< a\[j\] then the left subtree represents all the rest of the comparisons that we need to make, to finish the sort, and the leaves represent the permutations that we get after the sort. For example the left path for N = 4 is : (0:1), (1:2), (2:3), (0,1,2,3).

After I drew a tree for N = 4, the height was not 4, more specifically, an example would be the following path : (0:1),(1:2),(2:3), **here a\[2\] \> a\[3\]** (3:1),(3:0),(3,0,1,2). So is there a formula?

**In the example above we first find out that a\[0\] \< a\[1\] \< a\[2\] and then we find out that a\[2\] \> a\[3\], so we need to compare a\[3\] to a\[1\] and a\[0\], so far the path length is 4, but then we add the leaf (3,0,1,2) and now the path length is 5.**

# Answer
Basically, we just need to look at the worst case comparison number, a worst case comparison number is when we compare 1 with 2...N, then 2 with 3...N, etc. that will take (N^2 - N)/2 steps (arithmetic progression ((N-1)\*(N-1+1))/2). So that's the height of that tree.

So for N = 3 we get (3^3 - 3)/2 = (9 - 3)/2 = 3. For N = 4 we have (4^2 - 4)/2 = 6.
> 0 votes

---
Tags: complexity-theory, data-structures, sorting, binary-trees
---


title: set complement and superset

text:
# Question
Title: set complement and superset
`If 'S is a set complement of S, then a set complement of a superset of S' is a subset of S.`

Just want to verify that above is true just based on the definition of set complement and superset.

# Answer
Let $U$ be the universal set. We have $S\subseteq U$. The complement of $S$ is define as $S'=\\{x\in U\mid x\notin S\\}$. Thus $\forall x\in U,\\; x\in S'\text{ iff } x\notin S$.

Let $T$ be a superset of $S'$, $T\supseteq S'$, which is true iff $\forall x\in U,\\; x\in S'\text{ implies } x\in T$.

Then let $T'$ be the complement of $T$, so that again, as in the case of $S$, $\forall x\in U,\\; x\in T'\text{ iff } x\notin T$.

Now **you want to prove that $T'$ is a subset of $S$**, $T'\subseteq S$, which is true iff $\forall x\in U,\\; x\in T'\text{ implies } x\in S$.

Proof: Consider any element $x\in U$. Taking all our definitions in reverse order, we see that if $x\in T'$ then $x\notin T$. But this in turn that $x\notin S'$ since all elements in $S'$ are in its superset $T$. But by definition of $S'$, all elements not in $S'$ are in $S$.

So we have proved that $\forall x\in U,\\; x\in T'\text{ implies } x\in S$.

Hence $T'\subseteq S$.
> 0 votes

# Answer
I'm not sure what you mean by "a set complement of $S$."

If you mean to allow complements with respect to different universal sets, then the statement in the question is not true. For example, let $S=\\{1\\}$. Its complement $S'$ with respect to $\\{1,2\\}$ is $\\{2\\}$. $\\{1,2\\}$ is a superset of $S'$ but its set complement with respect to $\\{1,2,3\\}$ is $\\{3\\}$, which is not a subset of $S=\\{1\\}$.

On the other hand, if you mean "the set complement of $S$" with respect to some fixed universal set $U$,the statement is true. We have $S'=U\setminus S$ and choose some $T \supseteq S'$. Then $U\setminus T \subseteq U\setminus S' = S$.
> 0 votes

---
Tags: sets
---


title: bounded length CoNP proof

text:
# Question
Title: bounded length CoNP proof
**Question:** Let $A \subseteq $ {0,1}$^\* $ be a language which satisfies $|A \cap ${0,1}$^n|=n^3 $ for all $n\ge 10$ Prove that $A \in NP$ implies $A \in coNP$.

**Thoughts** I've been having difficulty with this problem. My idea is somehow showing that each set of $n^3$ words cannot be a verifier for A and therefore A is in coNP. The problem is that as I see it, proving this will take exp time as I have an exponential number of options for strings from which to choose n^3 from. Would like some suggestions about how to prove this.

# Answer
Assume that $A\in NP$, and let $V$ be a verifier for it. That is, $V$ takes as input $(x,y)$ and outputs 1 if $y$ witnesses that $x\in A$. That is, we can write $A=\\{x:\exists y,\ V(x,y)=1\\}$.

We show that $A\in coNP$, by showing that $\overline{A}\in NP$. We construct a verifier $V'$ for $\overline{A}$ as follows:

Given input $x$, $V'$ expects a witness of the form $(w\_1,y\_1,...,w\_{n^3},y\_{n^3})$, where $|x|=n$, such that $y\_i$ is a witness that $w\_i\in A$, and for every $i$ we have $w\_i\neq x$. That is, a witness for $x$ not being in $A$ is simply a list of all the $n^3$ words that *are* in $A$. Clearly verifying this can be done in polynomial time using $V$ (which we assume to run in polynomial time).
> 6 votes

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


# Question
Title: Huffman tree generation if the frequency is same for all words
Can a valid Huffman tree be generated if the frequency of words is same for all of them?

Example :

```
Value     | Frequency
--------------------
Google    | 2
Yahoo     | 2
Microsoft | 2
Amazon    | 2

```

# Answer
Yes. When creating a Huffman tree, if you ever find you need to select from a set of objects with the same frequencies, then just select objects from the set at random - it will have no effect on the effectiveness of the algorithm.

Of course, one might question *why* you're bothering to build a Huffman tree if you know all the frequencies are the same - I can tell you what the optimal encoding is.
> 2 votes

# Answer
Yes. Whenever identical frequencies occur, the Huffman procedure will not result in a unique code book, but all the possible code books lead to an optimal encoding.
> 2 votes

---
Tags: machine-learning
---


title: How to solve complexity problems

text:
# Question
Title: How to solve complexity problems
I have a problem in algorithm subject.. I have to decide whether 127n^2+n^3−4745n^2 is Ω(n^2) or not. How can I do this? Thanks very much!

# Answer
$127n^2+n^3−4745n^2$ is equal to $n^3−4618n^2$

There are constants $n\_0$ and $c$ such that $n^3−4618n^2 \geq \frac{1}{c}n^2$ for all $n \geq n\_0$, so $127n^2+n^3−4745n^2$ is $Ω(n^2)$.
> 1 votes

---
Tags: asymptotics
---


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

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

I was reading a paper that said:

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

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

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

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

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

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

# Answer
> 3 votes
I want to add some remarks that helped me understand (conceptually) much better what "*refuting* 3CNF" formulas meant (and thanks Yuval, his answer and discussion was useful, make sure you read it!).

First, want to point out what *refuting* means (this might have been an important (but easy to fix), confusion for me since English isn't my first language), *Refuting* means:

> prove (a statement or theory) to be **wrong** or **false**.

i.e. in the context of satisfiability, determining wether a formula is false (or unsatisfiable) is the same thing as *refuting* the (boolean) formula.

Hence, in this context, an algorithm A that refutes a random 3CNF (3-conjunctive normal form) formula means that the algorithm is able to determine wether the boolean formula is unsatisfiable or "it doesn't know".

A useful extract of the paper I am reading discusses this more precisely on page 5. For reference here is a screen shot of that discussion:

---
Tags: complexity-theory, logic
---


title: Is the empty set a dominating set?

text:
# Question
Title: Is the empty set a dominating set?
Is the empty set a *dominating set*?

I don't think it is, because in an empty set there are no vertices to dominate.

Is my reasoning correct?

# Answer
You are right in case that V is not empty. In case that V is empty the empty set is a Dominating set by definition.
> 1 votes

---
Tags: graphs
---


title: Kruskal's and Prim's algorithm

text:
# Question
Title: Kruskal's and Prim's algorithm
Does Kruskal's and Prim's algorithm work on directed graphs? I want the two algorithms to find a minimum spanning tree. For further enlightenment, I would like to know what other problems Kruskal's and Prim's can solve. So far, I only know they can solve minimum spanning trees. If it turns out there are an infinite number of problems Kruskal's and Prim's can solve, then no need to list all of them. I am learning this by myself and so far I only know one problem the two algorithms can solve.

I think that Prim's will not work because it is possible to have a node that points outwards to other nodes. If this central node is not chosen, then Prim's will be unable to give the MST including all the children.

I wonder if Kruskal's works. . . My counter example is a central node where all the children of the central node point to this central node. Running Kruskal's algorithm, we would get an MST that is not a shortest path, since we do not have path.

# Answer
By definition MST or Minimal spanning tree is defined on undirected graph only!

But if you are really want to (and I wander why) You can "make" Kruskal's algorithm work on it ,but you have to make sure you are ignoring loops because otherwise if you got a loop with small weight the algorithm will count it on the "MST" (because it isn't really MST).

Regarding to Prim's algorithm I can't see a way you cane make this work on directed graph.

I don't know other uses of Kruskal's and Prim's and I don't believe there are. Usually you make a slight changes on the algorithm in order to make them do something slight different.
> 1 votes

---
Tags: minimum-spanning-tree
---


# Question
Title: What is the name of this problem in Computer Vision?
My google skills have failed me during research for a college project. Our task is write a program that describes an image in spacial terms, e.g. "Cat on the left of a chair", or for a simple image "Two triangles over a large circle, and a sqaure underneath it".
Suppose that after analysing an image I have a set of objects, with names, coordinates, sizes, orientations. I want to transform this set into sentences like above, i.e. describing relative positions, overlaying and so on.
Unfortunately, I cannot find anything on this subject. "Scene decription" means 3D graphics description languages. "Image description" is about the nouns and, recently, the verbs describing an image. It seems that I have the wrong keywords.
I'd much appreciate any hints about what to look for. Links to scientific papers to peruse (if you have any at hand) would be great too.

# Answer
This seems to be exactly **scene description** as described, for example, in Timor Kadir's thesis:

> Broadly speaking, the aim of scene description is to arrive at a set of descriptions of a real world scene which *sufficiently* capture the component parts of the scene, their positions, poses, motions and interactions. (p. 3)
> 3 votes

---
Tags: artificial-intelligence, computer-vision
---


# Question
Title: Proving a language to be Recursively Enumerable?
I know to prove a language to be Recursively Enumerable, it is ideal to represent a Turing machine for it. Let L be set of strings which have alphabet {u,d,l,r}, where u is up 1, d is down 1, etc. L is representing paths on the Cartesian plane which can begin and end at any point so say begin at (1,3) and end back at (1,3). My Question is, you would be able to represent a Turing Machine for this, right? Hence it would be Recursively Enumerable.

# Answer
> 1 votes
Your language is computable, and so in particular recursively enumerable. Given a path on the Cartesian plane, you can decide whether it goes back where it started: just follow the path and see where it ends. You can program a computer to do that. So it is decidable.

---
Tags: graphs, computability, turing-machines, recursion-theory
---


# Question
Title: Why is one traversal sufficient for the Kuhn's maximal matching problem algorithm?
In Kuhn's algorithm for the maximum bipartite matching problem we iterate through the vertices of one partite set and try to build the increasing chain, starting with the current vertex. Once the traversal is completed, we claim that the maximal matching is found. But why don't we need to check again the vertices for which we weren't able to build the increasing chain? How can we prove that if for some vertex ***v*** it was not possible to build the increasing chain starting with ***v*** during the traversal, then we don't need to check ***v*** again? Why shouldn't we perform the second traversal?

# Answer
> 1 votes
Kuhn's algorithm maintains the following invariant: after scanning through vertices $v\_1,\ldots,v\_k$ on the left, the current matching is a maximal matching of the graph consisting of $v\_1,\ldots,v\_k$ on the left, and the entire right-hand side. Hence at the end, we get a maximal matching of the entire graph.

How do we know that Kuhn's algorithm maintains the invariant? We prove it when we prove that Kuhn's algorithm is correct. I encourage you to find a correctness proof of the algorithm (such proofs are surely not too hard to find online) and read it.

---
Tags: graphs, bipartite-matching
---


# Question
Title: Rigorous definition of efficient algorithm that $\epsilon$-refutes random 3CNF formulas
I recently asked a similar question, however, I'd like to address it in a more mathematically precise setting.

In that paper, on page 5, it talks about a rigorous definition of what it means to $\epsilon$-refute random 3CNF formulas. For that, I will provide a screenshot of the exact part I want to address:

> The problem of refuting random 3CNF concerns efficient algorithms that provide a proof that a random 3CNF is not satisfiable, or far from being satisfiable. This can be thought of as a game between an adversary and an algorithm. The adversary should produce a 3CNF formula. It can either produce a satisfiable formula, or produce a formula uniformly at random. The algorithm should identify whether the produced formula is random or satisfiable.
>
> Formally, let $\Delta\colon \mathbb N \to \mathbb N$ and $0 \leq \epsilon \< \frac14$. We say that an efficient algorithm $A$ *$\epsilon$-refutes random* 3CNF *with ratio $\Delta$* if its inputs is $\phi \in \mathrm{3CNF}\_{n,n\Delta(n)}$, its output is either "typical" or "exceptional", and it satisfies:
>
> * Soundness: If $\operatorname{Val}(\phi) \ge 1-\epsilon$ then $$ \Pr\_{\text{Rand. coins of $A$}}(A(\phi)=\text{"exceptional"}) \geq \frac34.$$
> * Completeness: For every $n$, $$ \Pr\_{\substack{\text{Rand. coins of $A$}\\ \phi \sim \operatorname{Uni}(\mathrm{3CNF}\_{n,n\Delta(n)})}}(A(\phi)=\text{"typical"}) \geq 1 - o(1). $$ By a standard repetition argument, the probability of $\frac34$ can be amplified to $1-2^{-n}$, while efficiency is preserved. Thus, given such an (amplified) algorithm, if $A(\phi)=\text{"typical"}$, then with confidence of $1-2^{-n}$ we know that $\operatorname{Val}(\phi) \< 1-\epsilon$. Since for random $\phi \in \mathrm{3CNF}\_{n,n\Delta(n)}$, $A(\phi)=\text{"typical"}$ with probability $1-o(1)$, such an algorithm provides, for most 3CNF formulas, a proof that their value is less than $1-\epsilon$.

The exact part I want to address is the properties soundness and completeness of the algorithms.

First, what does it mean that the output is "typical" or "exceptional"? I don't think the authors define that precisely. I am guessing from context, if the algorithm returns exceptional then it found a boolean formula that is unsatisfiable? Though I am just guessing from the definition of the word refute.

From the definition of $\operatorname{Val}(\phi)$ (=the fraction of clauses that are satisfiable, so its 1 when the whole thing is satisfiable) I am assuming that if the algorithm is sound then if it returns an answer, then the answer must be correct (i.e. the formula must be unsatisfiable). However, from the definitions given, it seems that if the formula is nearly satisfiable, then it says with high probability (greater than 3/4) that its "exceptional" (whatever that means)?

For completeness, what that usually means for me is that, if there is a correct answer, then the algorithm will return it. In this case, if we give it a boolean formula, if it's unsatisfiable, then it will say so. Thats what completeness usually means for me. In this case, the conditions given in the paper for completeness are hard for me to understand.

I think maybe the main source of confusion might be what the word "exceptional" and "typical" mean. My intuition says that most boolean formulas are unsatisfiable, so in fact, "exceptional" should mean satisfiable and "typical" means unsatisfiable? Which is kind of opposite of what a refuting algorithm would do in my head.

Anyway, anyone have any ideas of how to resolve this in a mathematically precise way?

# Answer
> 2 votes
The words "exceptional" and "typical" have absolutely no formal meaning. Let's rephrase the definition using two other words, "Clinton" and "Bush".

We say that a (possibly randomized) algorithm $A$ *$\epsilon$-refutes random 3CNF with ratio $\Delta$* if:

1. Given a 3CNF formula $\varphi$ with $n$ variables and $\Delta n$ clauses such that a $1-\epsilon$ fraction of the clauses (at least) is satisfiable, the probability that $A(\varphi)$ outputs "Clinton" is at least 75%.
2. With high probability, $A(\varphi)$ outputs "Bush" given a random 3CNF formula with $n$ variables and $\Delta n$ clauses.

What does the algorithm $A$ try to do? It tries to identify "Clinton" inputs, which are inputs that are at least $1-\epsilon$ satisfiable. At the same time, on a random input, which is with high probability not "Clinton", it should return "Bush". So it tries to separate the rare "Clinton" inputs from a random input.

---
Tags: complexity-theory, logic, randomized-algorithms
---


# Question
Title: Language of walks in a grid – context-free?
Consider the infinite two-dimensional grid with integer co-ordinates. A walk in the grid can be represented by a string over the alphabet $\\{u,d,l,r\\}$, where the letters stand for moving one square up, down, left and right, respectively.

Now consider the langauge of all strings representing closed walks (walks that end at their start point). To me, this would seem like any combination of $u$, $d$, $l$ or $r$. So would the language be represented as $L = \\{u,d,l,r\\}^\*$? If so, this wouldn't be context-free right? Thanks.

# Answer
> 7 votes
If your language $L$ were context-free then so would $L \cap u^\* l^\* d^\* r^\*$ be. However, $L \cap u^\* l^\* d^\* r^\* = \\{ u^n l^m d^n r^m : n,m \geq 0 \\}$, which is known not to be context-free (this can be proved using the pumping lemma).

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


# Question
Title: How do you produce a CNF from a circular graph with colouring?
If you had a circular graph e.g. A-\>B-\>C-\>D-\>E-\>A, and a legal coloring system with 3 colours (e.g. Red, Green Blue), where each node is assigned a colour and no node can be connected to another node of the same colour, what is the easiest way go about producing a Conjunctive Normal Form of node states (e.g. AR means A is coloured Red) where the models of the CNF correspond on a one to one basis to a legal colouring of the graph?

# Answer
> 1 votes
The easiest way is to solve the more general problem for (undirected) graphs and an arbitrary number of colors. Given a graph $G = (V,E)$ and a set of colors $C$, the formula has variables $x(v,c)$ for every vertex $v \in V$ and every color $c \in C$. There are clauses of three kinds:

1. For each vertex $v$, there is a clause $\bigvee\_{c \in C} x(v,c)$.
2. For each vertex $v$ and each pair of colors $c,d \in C$, there is a clause $\lnot x(v,c) \lor \lnot x(v,d)$.
3. For each edge $(v,w)$ and each color $c$, there is a clause $\lnot x(v,c) \lor \lnot x(w,c)$.

In words, these clauses state that:

1. Vertex $v$ gets some color.
2. Vertex $v$ gets at most one color.
3. Vertices $v,w$ (which are connected) don't get the same color.

---
Tags: graphs, boolean-algebra, colorings
---


# Question
Title: How does derandomization of 3SAT work via conditional expectations?
Given a single SAT clause with its 3 literals coming from 3 different variables it is obvious that a random assignment of values will satisfy it with probability 7/8

* But I do not understand how from the above argument it follows that given a $m$ clause SAT instance the probability of satisfying at least $7/8 - 1/2m$ fraction of the clauses is at least $1/poly(m)$ ?

\[..firstly even in a single clause case its not clear how the 7/8 result can hold if variables are repeated - and in the multi-clause case there will now be correlations across clauses - and hence its hardly clear to me as to what is happening!..\]

I believe there is some sort of a Markov inequality going on but I can't see it.

* Now apparently one can derandomize this using "conditional expectation". (vaguely I understand that it is some way of estimating what is the chance of satisfying the formula when randomizing over a subset of the variables while keeping the others' values fixed and then probably changing the subset in every round) This is totally unfamiliar to me as to how the above probabilistic argument can be converted into a deterministic one so as to ensure finding of an assignment of values to variables such that always at least 7/8 of the clauses are satisfied.

\[..apparently the above can also be thought via "3-wise independent sample space" - if someone can help understand that then that would be great!..\]

# Answer
> 2 votes
If you choose an assignment at random, each particular clause is satisfied with probability $7/8$. Using linearity of expectation, this shows that if you choose an assignment at random, then the number of satisfied clauses is at least $(7/8)n$. The idea is to have an indicator variable $X\_i$ for clause $i$, which states that the clause is satisfied. Since $\mathbb{E}\[X\_i\] = \Pr\[X\_i\] = 7/8$, by linearity of expectation we have $\mathbb{E}\[\sum\_{i=1}^m X\_i\] = (7/8)m$. In particular, some assignment satisfies at least $(7/8)m$ clauses.

Let now $X$ be the number of *unsatisfied* clauses under a random assignment. Then $\mathbb{E}\[X\] = (1/8)m$, and so Markov's inequality shows that $$ \Pr\[X \geq (C/8)m\] \leq 1/C. $$ By choosing an appropriate $C$ you get your first bullet (try it out!).

Regarding the method of conditional expectations, there are many online resources, for example this one (the first hit on a popular search engine). There are many others.

Finally, if $\mathcal{D}$ is a 3-wise independent sample space – this just means that if $(v\_1,\ldots,v\_n) \sim \mathcal{D}$, then for any $i\<j\<k$, the joint distribution of $(v\_i,v\_j,v\_k)$ is uniform over all eight possibilities – then it is still the case that each clause is satisfied with probability exactly $7/8$ (why?). Therefore if we choose a random assignment according to $\mathcal{D}$, the expected number of satisfied assignments is exactly $(7/8)m$. In particular, some assignment in the support of $\mathcal{D}$ – that is, an assignment which is generated by $\mathcal{D}$ with some probability – satisfies at least $(7/8)m$ clauses.

Why is this helpful? There are 3-wise independent samples spaces of polynomial size. We can derandomize the random 3SAT algorithm by taking such a sample space and trying out all assignments in its support. One of them will satisfy at least $(7/8)m$ clauses.

---
Tags: complexity-theory, np-complete, satisfiability, probability-theory, randomized-algorithms
---


# Question
Title: Efficient algorithms for vertical visibility problem
During thinking on one problem, I realised that I need to create an efficient algorithm solving the following task:

**The problem:** we are given a two-dimensional square box of side $n$ whose sides are parallel to the axes. We can look into it through the top. However, there are also $m$ horizontal segments. Each segment has an integer $y$-coordinate ($0 \le y \le n$) and $x$-coordinates ($0 \le x\_1 \< x\_2 \le n$) and connects points $(x\_1,y)$ and $(x\_2,y)$ (look at the picture below).

We would like to know, for each unit segment on the top of the box, how deep can we look vertically inside the box if we look through this segment.

*Formally, for $x \in \\{0,\dots,n-1\\}$, we would like to find $\max\_{i:\ \[x,x+1\]\subseteq\[x\_{1,i},x\_{2,i}\]} y\_i$.*

*Example: given $n=9$ and $m=7$ segments located as in the picture below, the result is $(5, 5, 5, 3, 8, 3, 7, 8, 7)$. Look at how deep light can go into the box.*

Fortunately for us, both $n$ and $m$ are *quite* small and we can do the computations off-line.

The easiest algorithm solving this problem is brute-force: for each segment traverse the whole array and update it where necessary. However, it gives us not very impressive $O(mn)$.

A great improvement is to use a segment tree which is able to maximize values on the segment during the query and to read the final values. I won't describe it further, but we see that the time complexity is $O((m+n) \log n)$.

However, I came up with a faster algorithm:

**Outline:**

1. Sort the segments in decreasing order of $y$-coordinate (linear time using a variation of counting sort). Now note that if any $x$-unit segment has been covered by any segment before, no following segment can bound the light beam going through this $x$-unit segment anymore. Then we will do a line sweep from the top to the bottom of the box.
2. Now let's introduce some definitions: $x$-unit segment is an imaginary horizontal segment on the sweep whose $x$-coordinates are integers and whose length is 1. Each segment during the sweeping process may be either *unmarked* (that is, a light beam going from the top of the box can reach this segment) or *marked* (opposite case). Consider a $x$-unit segment with $x\_1=n$, $x\_2=n+1$ always unmarked. Let's also introduce sets $S\_0=\\{0\\}, S\_1=\\{1\\}, \dots, S\_n=\\{n\\}$. Each set will contain a whole sequence of consecutive *marked* $x$-unit segments (if there are any) with a following *unmarked* segment.
3. We need a data structure that is able to operate on these segments and sets efficiently. We will use a find-union structure extended by a field holding the maximum $x$-unit segment index (index of the *unmarked* segment).
4. Now we can handle the segments efficiently. Let's say we're now considering $i$-th segment in order (call it "query"), which begins in $x\_1$ and ends in $x\_2$. We need to find all the *unmarked* $x$-unit segments which are contained inside $i$-th segment (these are exactly the segments on which the light beam will end its way). We will do the following: firstly, we find the first *unmarked* segment inside the query (*Find* the representative of the set in which $x\_1$ is contained and get the max index of this set, *which is the unmarked segment by definition*). Then this index $x$ is inside the query, add it to the result (the result for this segment is $y$) and mark this index (*Union* sets containing $x$ and $x+1$). Then repeat this procedure until we find all *unmarked* segments, that is, next *Find* query gives us index $x \ge x\_2$.

Note that each find-union operation will be done in only two cases: either we begin considering a segment (which can happen $m$ times) or we've just marked a $x$-unit segment (this can happen $n$ times). Thus overall complexity is $O((n+m)\alpha(n))$ ($\alpha$ is an inverse Ackermann function). If something is not clear, I can elaborate more on this. Maybe I'll be able to add some pictures if I have some time.

Now I reached "the wall". I can't come up with a linear algorithm, though it seems there should be one. So, I have two questions:

* Is there a linear-time algorithm (that is, $O(n+m)$) solving the horizontal segment visibility problem?
* If not, what is the proof that the visibility problem is $\omega(n+m)$?

# Answer
> 1 votes
1. First sort both $x1$ and $x2$ coordinates of the lines in two seperate arrays $A$ and $B$. $O(m)$
2. We also maintain an auxilary bit array size $n$ to keep track of the active segments.
3. Start sweeping from the left to right:
4. for $(i=0,i\<n,i++)$
5. {
6. ..if $\exists x1=i$ with $y$ value $c$ $O(1)$
7. ..{
8. ....find($\max$)
9. ....store($\max$) $O(1)$
10. ..}
11. ..if $\exists x2=i$ with $y$ value $c$ $O(1)$
12. ..{
13. ....find($\max$)
14. ....store($\max$) $O(1)$
15. ..}
16. }

find($\max$) can be implemented using an bit array with $n$ bits. Now whenever we remove or add an element to $L$ we can update this integer by setting a bit to true or false respectively. Now you have two options depending on the programming language used and the assumption $n$ is relatively small i.e. smaller than $long long int$ which is at least 64 bits or a fixed amount of these integers:

* Get the least significant bit in constant time is supported by some hardware and gcc.
* By converting $L$ to an integer $O(1)$ you will get the maximum (not directly but you can derive it).

I know this is quite a hack because it assumes a maximum value for $n$ and hence $n$ can be seen as a constant then...

# Answer
> 0 votes
I don't have a linear algorithm, but this one seems to be O(m log m).

Sort the segments based on the first coordinate and height. This means that (x1, l1) always comes before (x2, l2) whenever x1 \< x2. Also, (x1, l1) at height y1 comes before (x1, l2) at height y2 whenever y1 \> y2.

For every subset with the same first coordinate, we do the following. Let the first segment be (x1, L). For all other segments in the subset: If the segment is longer than the first, then change it from (x1,xt) to (L, xt) and add it to the L-subset in the proper order. Otherwise drop it. Finally, if the next subset has a first coordinate less than L, then split the (x1,L) to (x1, x2) and (x2, L). Add the (x2, L) to the next subset in the correct order. We can do this because the first segment in the subset is higher and covers the range from (x1, L). This new segment may be the one which covers (L, x2), but we won't know that until we look at the subset which has first coordinate L.

After we run through all of the subsets, we will have a set of segments which don't overlap. To determine what the Y value is for a given X, we only have to run through the remaining segments.

So what is the complexity here: The sort is O(m log m). Looping through the subsets is O(m). A lookup is also O(m).

So it seems that this algorithm is independent of n.

---
Tags: algorithms, data-structures, time-complexity, computational-geometry
---


# Question
Title: Which optimization algorithm would you recommend for this small multidimensional problem?
Which algorithm would be suitable for finding or estimating the vector $$\mathbf{s}\_{opt}=\begin{bmatrix} s\_1 & \cdots & s\_N \end{bmatrix}=\arg\max\_{\mathbf{s}}\sum\_{n=1}^{N}p\_{s\_n,n}$$ under the constraint $$\sum\_{n=1}^{N}l\_{s\_n,n}\leq L\_{max}$$ given known values for the integer $N$, the vector $\mathbf{p}\_n=\begin{bmatrix} p\_{1,n}\\ \vdots \\ p\_{M\_n,n} \end{bmatrix}$, the vector $\mathbf{l}\_n=\begin{bmatrix} l\_{1,n}\\ \vdots \\ l\_{M\_n,n} \end{bmatrix}$, the integer $L\_{max}$ and all integers $M\_n$?

Here are some restrictions showing that the size of the problem isn't very big: $$N\\:\epsilon\\:\mathbb{Z}\\:|\\:0\<N\<50$$ $$p\\:\epsilon\\:\mathbb{R}\\:|\\:0\leq p\_{m,n}\leq 1\\:|\\:p\_{1,n}=1\\:|\\:p\_{M\_n,n}=0$$ $$l\\:\epsilon\\:\mathbb{Z}\\:|\\:0\leq l\_{m,n}\leq 30\\:|\\:l\_{M\_n,n}=0$$ $$M\_n\\:\epsilon\\:\mathbb{Z}\\:|\\:2\leq M\_n \leq 20$$

Another circumstance which may be of interest is that the problem will be solved repeatedly. In the first iteration $N=1$ and then for each iteration $N$ will increase as per the sequence $N=1,2,3,...$. The vectors $\mathbf{p}\_n$ and $\mathbf{l}\_n$, as well as the other inputs, will remain unchanged for all iterations $N=1,2,3,...$, meaning that the same problem just grows slightly step by step.

I am planning to implement this algorithm in JavaScript.

**Edit: Real-world case**

The mathematical optimization problem above has its origin in a real world (however, stupid) problem. Assume you need to communicate a text of $N$ words, but you have a limited total amount of characters to use, $L\_{max}$. For each word $n$ you have found $M\_n$ number of alternative representations (such as acronyms and synonyms) each with a probability of the reader to understand approximated to $p\_{m,n}$. Now the goal is to choose which representation $s\_n$ of each word should be chosen in order to maximize the probability of the receiver to understand the text. This probability can be approximated to the mean value all individual word probabilities.

# Answer
This problem is effectively knapsack, where the size of the knapsack is $L\_{max}$. The items are $1,\ldots,n$, and for each item $i$ we can select a quantity (to include in our knapsack) of $j\in\\{2,\ldots,M\_n\\}$. Taking quantity $j$ of item $i$ gives reward $p\_{j,i}$ and takes up $l\_{j,i}$ space in the knapsack.

Let $D(n,r)$ be $max\_s \sum\_{i=1}^{n} p\_{s\_i,i}$ under the constraint that $\sum\_{i=1}^{n} l\_{j,i} \leq r$. $D(N,L\_{max})$ (which is the value you're after) can be computed in $O(L\_{max}\cdot NM)$ time (where $M$ is $max\_i M\_i$) using dynamic programming.

Effectively $D(n,r)$ represents the best way (mean probability) to represent the first $n$ words using at most $r$ space. The best way to represent $D(n,r)$ is to combine some choice of representing word $n$ with the best way to represent the remaining $n-1$ words in however many characters are left. This is expressed by the recurrence relation:

$$D(n,r)=max\_{s\_n\in\\{2,\ldots,M\_n\\}} p\_{s\_n,n} + D(n-1,r-l\_{s\_n,n})$$

Where $D(\*,r)=-\infty$ if $r\<0$ and $D(0,\*)=0$.

What is very important is that you store (and reuse) the intermediate values of $D(n,r)$ during the computation, as this will save significantly on computation time. Reusing these values will also allow you to deal with the growing input requirement, since the values encountered when computing $D(n,\*)$ can be reused when computing $D(n+1,\*)$.
> 4 votes

---
Tags: algorithms, optimization, discrete-mathematics
---


title: Simplying this regular expression

text:
# Question
Title: Simplying this regular expression
I am trying to prove (without converting it into Automata, through just simplification) that the following two regular expressions are equal:

$ (\epsilon + 0^\*1^+0)^\* = \epsilon + (0+1)^\*10 $

here is what I have got so far:

$$ (\epsilon + 0^\*1^+0)^\* = \\ (0^\*1^+0)^\* = \\ (0^\*1^\*10)^\* = \\ \epsilon + (0^\*1^\*10)^+ = \\ \epsilon + (0^\*1^\*10)(0^\*1^\*10)^\* = \\ \epsilon + 0^\*1^\*10(0^\*1^\*10)^\*$$

I seem to be stuck, I am not sure if I am doing it the correct way, or if there is a better way to prove this.

I know that $(a+b)^\* = (a^\*b^\*)^\* $ is true and I think this will certainly come in handy for the problem above but I am not sure how to prove $(a+b)^\* = (a^\*b^\*)^\* $ either.

# Answer
The regular expression on the right consists of the empty word along with all words ending in $10$. All words accepted by the regular expression on the left are of this form. It remains to show that all words accepted by the regular expression on the right are also accepted by the one on the left. This is clear for the empty word, so it remains to show the following:

> Every word ending in $10$ is accepted by $(0^\*1^+0)^\*$.

Indeed, every word ending in $10$ has the form $$ 0^{a\_1} 1^{b\_1} 0^{a\_2} 1^{b\_2} \cdots 0^{a\_n} 1^{b\_n} 0, $$ where $b\_1,a\_2,b\_2,\ldots,a\_n,b\_n \geq 1$. We can decompose this word as $$ (0^{a\_1} 1^{b\_1} 0) (0^{a\_2-1} 1^{b\_2} 0) (0^{a\_3-1} 1^{b\_3} 0) \cdots (0^{a\_{n-1}-1} 1^{b\_n} 0) \in (0^\*1^+0)^\*. $$
> 0 votes

---
Tags: regular-expressions
---


# Question
Title: Page Table Size in a 4 Level Hierarchical Page Table
> An Intel 64 bit CPU uses a four-level hierarchical page table. Each of the four levels of the page table can contain 512 entries, and the page table size is 4KB. You should be able to see that it cannot actually address 2^64 bytes of virtual memory. If a process on the system used 12MB of text, 5MB of heap and 7MB of stack, calculate the page table size, the number of page table entries required and the number of second level page tables.

**Disclaimer: This question is not from an academic assessment. It is a past paper question in preparation for an examination.**

If the page table size is 4096 bytes then $\log\_2(4096) = 12$. Thus, the offset is 12 bits. Since there are 4 levels in this page table and each level can support 512 entries, the index into each entry is $\log\_2(512) = 9$. Thus, you have 4x 9 bit indexes in the virtual address and a 12 bit offset.

One question arises: $9 * 4 + 12 = 48$ bits. But we have 64 bit virtual addresses? What happens to the other 16 bits? I would assume these are zeroed as the 16 most significant bits. Is that correct?

If this is true, does that mean this paging system can address 2^36 pages of virtual and physical memory, and therefore, it can address at most 2^48 bytes of virtual and physical memory. Is that correct?

Under the assumption outlined above: 12MB of text requires 3072 pages, 5MB of heap requires 1280 pages and 7MB of stack requires 1792 pages.

We know that the address space looks like this:

```
|----------| 2^36
|  Stack   | (Stack expands down)
|          |
|          |
|          |
|   Heap   | (Heap expands up)
|   Text   |
|----------| 0x0

```

Since the stack is at the top of the address space, it must have it's own second level page table. However, the program text and heap are at the bottom of the address space. Since each second level page table can address 512GB of memory (512^3 * 4096) the program text and heap can share a second level page table. Then, since each third level page table can address 1GB (512^2 * 4096) the program text and heap can share a third level page table too. Thus, we have 18 page table entries. Since this is a 64 bit architecture, each page table consumes 64 bits, and therefore the size of the page table is $18 * 512 * {64 \over 8} = 72KB$.

4th level can address $512 \times 4096$ bytes,

3rd level can address $512^2 \times 4096$ bytes,

2nd level can address $512^3 \times 4096$ bytes,

1st level can address $512^4 \times 4096$ bytes.

```
     L1       L2       L3       L4
2^32 |---|--->[---]--->[---]--->[---]   }
     |---|                  --->[---]   }  7MB STACK
     |---|                  --->[---]   }
     |---|                  --->[---]   }
     |---|
     |---|
     |---|
     |---|
     |---|                      L4
     |---|                      |->[---] }
     |---|                      |->[---] } 5MB HEAP
     |---|    L2       L3       |->[---] }
   0 |---|--->[---]--->[---]--->|
                                |->[---] }
                                |->[---] }
                                |->[---] } 12MB TEXT
                                |->[---] }
                                |->[---] }
                                |->[---] }

Key [---] Level in Page Table
     ---> Pointer to Lower Level Page Table

```

# Answer
> 3 votes
The virtual addresses must be canonical, the top 16 bits are all copies of the 48th bit. Using a non-canonical address (in the sense of using it as an address) generates a #GP. See also, the manual, volume 3, chapters 3 and 4.

That is independent from the maximum physical address, which is not "canonical" in that way but just goes from 0 to some large number determined by MAXPHYADDR. You can find MAXPHYADDR using CPUID:80000008H, the lowest 8 bits in `eax`. It specifies the bit index in the page table entries (and some other places where you specify a physical address) at which the physical address stops and the reserved region begins. It's at least 36. It *could* be 48, but that wouldn't have anything to do with the limits on virtual addresses. The page table entry format allows it to go up to 52 (allowing you to address 4PB of RAM), but that hasn't happened yet. Intel seems to like 39 and 46, AMD seems to mostly use 48 now (they've used lower in the past) (source).

---
Tags: virtual-memory, paging
---


# Question
Title: Combinatorial optimization problem - What would you call this?
I'm trying to solve an optimization problem which can be described as follows.

* There are four sets objects. For simplicity, let's call them :
    1. Apples
    2. Oranges
    3. Pears
    4. Lemons
* The sets can contain unequal numbers of their respective objects
* These objects must be organized into groups containing exactly one of each object
* Each possible group can be evaluated by some merit function (ie: function of the difference between the masses of the constituent objects of the group, say)
* The maximum number of groups with a merit function below some threshold must be formed with the objects in the input sets.
* In the above set of groups, no object can be duplicated - it must belong uniquely to one group.

My question is not necessarily how to solve this problem - this is no doubt an extremely broad question. What I would like to know is **whether or not this problem has, or is of a class of problem, with some formal name**.

Primarily, I'm looking for search terms to help research similar problems (and the types of solutions that are known for it).

# Answer
> 3 votes
It's called four-dimensional matching and it's **NP**-complete.

---
Tags: algorithms, optimization, combinatorics
---


# Question
Title: Proving NP completness without reductions
What methods are there to prove a language is NP-complete? I already know the reduction method, but are there more sophisticated/advanced methods to prove this?

# Answer
> 5 votes
To prove that a problem is **NP**-complete, you must show that it's in **NP** and that every problem in **NP** reduces to it. As far as I'm aware, there are only really two ways of doing the latter:

* show that some problem already known to be **NP**-complete reduces to your problem;
* show directly that every problem in **NP** reduces to your problem by showing that your problem can essentially simulate a nondeterministic polynomial-time Turing machine.

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


# Question
Title: Undecidable definition of pure function?
I am trying to come up with a formal definition for functional purity in a simple programming language (think JavaScript). What I've got so far is this:

> **DEFINITION**: A statement is *impure* if
>
> * it is an assignment, unless it assigns to a local variable
> * OR, it evaluates a call to a function, unless that function is pure
> * OR, it is a block containing an impure statement
>
> **DEFINITION**: A function is *pure* if it doesn't contain any impure statement.

For simplicity, let's ignore *assignments* altogether and assume that a *block* is simply an ordered set of statements. (it shouldn't make a difference)

Now, this definition seems to work great until somebody defines a function that refers to itself, e.g.

```
function fibonacci(n)  {
    if(n == 0)
        return 0;
    else if(n == 1)
        return 1;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

```

or

```
function f() { return g(); }
function g() { return f(); }

```

By the proposed definition, to prove that *fibonacci* is pure, you need to prove that *fibonacci* is pure. Similarly in the second example. Thus, the purity of *fibonacci*, *f* and *g* is undecidable, yet intuitively we know that all 3 of these are pure, so this definition must be flawed.

How would I modify this definition to be decidable (and give the intuitively expected answer) even in the presence of recursion?

This question refers to some definitions of functional purity, but they don't seem formal enough to be used as a base for further reasoning.

# Answer
> 6 votes
## On undecidability

You attempt to prove that `fibonacci` is pure in a particular way, and you fail to do so. This does not prove that purity is an undecidable property. All it shows is that this particular way of determining the purity of `fibonacci` doesn't work.

A property is undecidable if *no matter what method you use to calculate it*, there is a parameter for which it fails. The possible methods are algorithms implemented on a Turing machine or any equivalent framework (recursive functions, etc.).

Purity is undecidable in general, but you need more language constructs than what you showed. For example, it is easy to reduce purity to halting, which is a well-known undecidable problem:

```
f;
global := 3;

```

This code is pure iff `global := 3` is never executed, which is equivalent to saying that `f` doesn't terminate. So if you can decide purity, you can decide halting.

## On recursive definitions

Your definition of purity is incomplete. You need to explain in more detail how to deal with recursive functions. To illustrate this, let's consider the following axioms for a property which I'll call *cuteness*:

* If `A` and `B` are cute then `A; B` is cute.
* If `A`, `B` and `C` are cute then `if A then B else C` is cute.
* If `A`, `B1`, …, `Bn` are cute then `A(B1,…,Bn)` is cute.
* `+`, `-`, `==` are cute.

Is `fibonacci` cute? If the list of axioms above is *complete*, then no, `fibonacci` is not cute, because a recursive function definition is not cute. All of the axioms above work if I replace “cute” by “terminating”, which shows that adding recursive functions to the mix can radically change the definition.

If I add the following axiom:

* If `A` is cute then `function f () { A }` is cute.

Then all cute functions are, in fact, pure in the sense of not having assignments as side effects. The axioms above in fact completely capture a strong notion of purity, i.e. if a function is pure then you can prove it using these axioms. The notion of purity defined here forbids all assignments, even if they don't escape their scope.

## On defining purity

If you want to allow internal side effects, you need a more complex definition, with a *context*. Above all axioms were of the form “if these programs have the property then that program has the property too”. More complex properties need to consider programs in context, to describe the variables, types, memory locations, etc. used in the program. The following rules capture purity in a context which defines what variables are allowed to be modified:

* If `A` and `B` are pure in the context `Γ` then so is `A; B`.
* If `A`, `B` and `C` are pure in the context `Γ` then so is `if A then B else C` is cute.
* If `A`, `B1`, …, `Bn` are cute in the context `Γ` then so is `A(B1,…,Bn)`.
* `+`, `-`, `==` are pure in any context.
* If `A` is pure in the context `Γ` then `A` is also pure in any superset of `Γ`.
* If `A` is pure in the context `Γ, x1,…,xn` then `function f (x1,…,xn) { A }` is pure in the context `A`.
* If `A` is pure in the context `Γ` then `x := A` is pure in the context `Γ, x`.

A better way to say “`A` is pure in the context `Γ`” might be “`Γ` captures all the side effects of `A`”. A program is pure if the empty context captures its side effects.

---
Tags: formal-languages, logic, undecidability, recursion
---


title: Decidable Problem

text:
# Question
Title: Decidable Problem
How should I go about showing that the following problem is decidable:

```
            Given DFAs M1 and M2, is L(M1) ⊆ L(M2)?

```

What is the general strategy to prove that a problem is decidable or undecidable?

Thanks in advance.

# Answer
It is decidable.

First, deciding whether the language of a DFA is empty or not is decidable (by checking if there is a path from the initial state to an accepting state).

Next, a hint:

> construct a DFA that accept all the words accepted by M1 that are not accepted by M2.
> 1 votes

---
Tags: undecidability, decision-problem, halting-problem
---


# Question
Title: Estimate distribution of a composite variable
Suppose I have N sets of numbers (10 numbers per set) {a1, ....., a10}. I form a sum by taking one number at random from each set. SUM = num from set 1 +......+ num from set N. If I do this a large number of times I will generate a large number of different values for the SUM variable. How can I estimate the distribution of the SUM values (P10, P50, P90 etc.)?

# Answer
> 1 votes
Use a convolution.

For instance, write the generating function for each set, then multiply the generating functions; this gives you the generating function for the distribution of the sum.

This gives you the exact distribution (which is even better than an approximation!).

---
Tags: probability-theory, randomness, sampling
---


# Question
Title: What does least fix point and greatest fix point mean in Safety games
In safety games there are these mathematical notation about greatest fix points and least fix points but I don't get it. How would we describe them plain English without mathematical symbols.

# Answer
> 9 votes
Probably the most common fixpoint expressions in model checking are things like $\mu X.A\cup(B\cap\circ X)$ and $\nu X.A\cap(B\cup\circ X)$, where $\circ$ is some flavour of "next state" operator. That is, the least $X$ such that $X = A\cup(B\cap\circ X)$, and the greatest $X$ such that $X = A\cap(B\cup\circ X)$, respectively. More generally, we are talking about fixpoints of monotonic *set transformers*, i.e. functions $P({\cal S})\to P({\cal S})$ operating on the subsets of a given set $\cal S$.

An intuitive way of thinking about *least* fixpoints is that they represent sets constructed bottom-up using constructors. Suppose you wanted to define the natural numbers as a subset of the reals: $n$ is a natural number iff it is $0$, or the successor of another natural number. This means that $\mathbb{N}$ is a fixpoint of the set transformer $F:S\mapsto\\{0\\}\cup succ(S)$. This is not enough, though: the set of all real numbers is also such a fixpoint. $\mathbb{N}$ is the *least* fixpoint, though, meaning that it only contains those elements which it has to in order to be a fixpoint. Computationally, this fixpoint is the limit you obtain by iterating the given set transformer $F$ on the empty set, gradually assembling the elements of $S$, i.e. the limit of $\emptyset,F(\emptyset),F(F(\emptyset)),\dots$.

In the case of $S:=\mu X.A\cup(B\cap\circ X)$ this means that $S$ contains exactly those elements which can reach $A$, satisfying $B$ until they get there; not requiring the least fixpoint would mean that you could additionally have arbitrary $B$-cycles, infinite $B$-paths never satisfying $A$, etc in your set.

For *greatest* fixpoints, you have the dual situation: the set contains all elements which are not explicitly eliminated by the given conditions. For $S=\nu X.A\cap(B\cup\circ X)$, this includes any element which satisfies $A$, and either also satisfies $B$ or has a successor in $S$. We pick the greatest fixpoint because we want to include everything which doesn't violate the requirements. Otherwise we might end up with an excessively restrictive set (such as the least fixpoint, which is just $A\cap B$ in this case). Computationally, this is the limit you get by iterating the transformer on the full set $\cal{S}$ of states, gradually eliminating all which fail the specification, i.e. the limit of ${\cal S},F({\cal S}),F(F({\cal S})),\dots$.

# Answer
> 3 votes
A fixed point of a function $f$ is a value $x$ such that $f(x)=x$. A function might have no fixed points (e.g., $f(x)=x+1$), a finite number of them (e.g., $f(x)=x^2+x-1$) or infinitely many (e.g., $f(x)=x$ where $x$ comes from some infinite set).

If $x$ comes from a set with an ordering relation, such as $\leq$ on some kind of numbers, or $\subseteq$ on sets and a function $f$ has at least one fixed point, it makes sense to talk about the least or greatest fixed point of $f$ with respect to that ordering. For example, on the real numbers, the fixed points of $f(x)=x^2+x-1$ are $x=\pm 1$: the greatest fixed point is $+1$ and the least fixed point is $-1$.

I suspect the functions you're dealing with aren't functions on the real numbers but the same principles apply.

---
Tags: terminology, formal-methods, model-checking, mu-calculus
---


title: simulation of PDA with turing machine

text:
# Question
Title: simulation of PDA with turing machine
How to simulate a non-deterministic PDA with a turing machine?

# Answer
The sets of all languages that can be represented by a PDA is proper subset of the all languages that can be represented by a Turing Machine.

Turing Machine can imitate any solution for the problem that can be solved.

The high level definition of the Turing Machine that simulates PDA as follows:

> A language is context free if and only if some PDA recognize it. (It is provable)
>
> $A\_{CFG}$ is a decidable language.(It is also provable)
>
> The TM $S$ for $A\_{CFG}$ follows.
>
> $S$ = "On input $\<G,w\>$, where $G$ is a CFG and $w$ is a string:
>
> 1. Convert $G$ to an equivalent grammar in Chomsky normal form.
> 2. List all derivations with $2n-1$ steps, where n is the length of $w$; except if $n=0$, then instead list all derivations with one step.
> 3. If any of these derivations generate $w$, $accept$; otherwise, $reject$."
> 3 votes

# Answer
A PDA is a special (degenerated) case of a TM. Specifically, TM can be seen as a PDA whose stack's head can read from within the stack and not only the top of the stack.

Therefore, simulation of a PDA by a TM is trivial.
> 3 votes

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


# Question
Title: Identifying and describing the language accepted by a Turing machine
Given a Turing machine, how can I identify the language it accepts and write a set notation for L(M)?

# Answer
A Turing machine implements an algorithm. The algorithm can be implicit by an explicit definition of the language such as:
$M$ is a TM such that $L(M)=\left \\{ x\in \Sigma^\* \ | \ |x|\in \mathbb{N}\_{even}\right \\}$. Which is usually the case.
In other cases, you might have to understand a turing machine based on a state diagram, this will be a simple reverse engineering problem where based on some inputs you understand the algorithm (and then you can prove your assumption).
Generally, there is no fixed approach towards understanding the language a machine accepts.
> 3 votes

# Answer
The problem of identifying the language that is accepted by a Turing machine (using or not some form of set construction notation) does not have a general solution. This means that - with the exception of a minority of trivial cases - you will have to take them one at a time, as separate problems, *by logical necessity*.

The fact that this question constantly reappears (in different guises) just shows how its answer is counterintuitive. It may be worth noting that Turing proposed the model of computation that carries his name precisely to explore the limits of computation, so this negative result should not be treated as something unexpected, or surprising.
> 1 votes

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


# Question
Title: Closure properties of linear context-free languages
Under what operations are linear context-free languages closed? Suppose $L\_1, L\_2$ are two linear context free languages. Are there any guarantees about $L\_1 \cup L\_2$, $L\_1 \cap L\_2$, $\overline{L\_1}$, $L\_1 . L\_2$, etc.?

# Answer
> 8 votes
For our readers. Linear grammars are close to regular grammars, a single nonterminal at the time, but they may generate letters at both sides $A \to aBb$ with $A,B$ nonterminal, and $a,b$ terminal (or empty). $REG \subset LIN \subset CF$, strict. Some closure proofs may benefit from another way to define linear languages: as single turn pushdown languages.

Linear languages are closed under union, construction as for context-free grammars $S\to S\_1, S\to S\_2$. Likewise they are closed under intersection with regular languages.

They are not closed under intersection: $\\{ a^n b^n c^m \mid m,n \ge 0 \\} \cap \\{ a^n b^m c^m \mid m,n \ge 0 \\}$.

Hence they cannot be closed under complement, but I would be nice to have a concrete example.

Neither are they closed under concatenation, intuitively because $S\to S\_1S\_2$ is not a linear structure. Same for Kleene star.

Linear languages have a pumping property which is similar to that of the context-free languages, except that the composition $z = uvwxy$ may additionally be required to have $|uvxy|\le m$, where $m$ is the pumping constant. This is similar to the requirement for regular languages, where pumping may be assumed to be at the beginning. Linear languages also have a linear structure (like finite state computations) but the symbols that are generated first are at both ends of the string. WIth this property it can be easily shown that $K =\\{a^nb^n \mid n\ge 1\\}^2$ is not linear.

Both regular and context-free are closed under rotation, but linear languages are not: $K$ is the rotation of linear $\\{ b^m a^n b^n a^m \mid m,n\ge 1 \\}$ (and a suitable regular intersection).

Regular languages are closed under quotient, but linear (and context-free) languages are not. In fact the operation is very powerful: the RE languages are quotients of two linear languages.

On the other hand, they are closed under quotient with regular languages. That follows as they form a *full trio* (i.e., they are closed under homomorphisms, and inverse morphisms and intersection with regular languages). Consequently/equivalently they are closed under finite state transductions.

Of course, they are closed under reversal.

---
Tags: formal-languages, formal-grammars, closure-properties, linear-languages
---


# Question
Title: Converting a NFA to its equivalent regular expression
I'm new to regular expressions and I'm currently working on some exercises on converting DFA's and NFA's into their equivalent regular expressions.

I have the following NFA:

I'm using the **state elimination method** to obtain the regular expression for the NFA. So I first introduced two new states, $q\_{start}$ (the new start state of the NFA) and $q\_{end}$ (the new and only accepting state of the NFA). After that, I eliminated the states one after the other.

To eliminate the states, I pick a state $p\_e$ to be eliminated. Then for every pair $(p\_1,p\_2)$ with $p\_1, p\_2 \neq p\_e$ and transitions from $p\_1$ to $p\_e$ and from $p\_e$ to $p\_2$, I determine the labels $r\_0,r\_1,r\_2,r\_3$ of this general automaton

wipe out $p\_e$ and replace $(p\_1,r\_0,p\_2)$ with $(p\_1,r\_0+r\_1 r^{\*}\_2r\_3,p\_2)$.

I already eliminated states $q\_0$ and $q\_1$, but I have no idea how to eliminate state $q\_4$, since it has no outgoing transitions except to itself. Could you please help me out with that?

# Answer
Technically it *can* be reduced, by introducing a regular expression for the empty set, which represents the missing edge.

However, $q\_4$ is completely useless for the language. They can be dropped without changing the accepted language. That should save some work.
> 3 votes

---
Tags: formal-languages, automata, regular-expressions
---


# Question
Title: Basic question about backjumping in SAT solvers
I am reading "Formalization and Implementation of Modern SAT Solvers", by Filip Marić.

My question is about how backjumping is defined. In an example \[1\], there is a conflict clause C equal to

\[-1,-2,-3\]

that has already been explained and learned. The decision trail is

|6, 1, 2, |7, |3, 4, 5,

where true decisions are marked with | and the others are propagated literals.

Then the algorithm performs a backjump to the level of literal 2, the most recently asserted literal that makes the conflict clause a unit clause. This modifies the decision trail to

|6, 1, 2

and immediately propagates -3 since \[-1,-2,-3\] is unit now, obtaining

|6, 1, 2, -3

What I would like to understand is: why not define backjumping so that the choice of 7, and all the (potential) work performed after it, were preserved? In this example, choosing 7 didn't do much, but it could have done a lot of propagation that we would not want to waste. There could also be other choices between 7 and -3 that we would benefit from preserving. It seems to me that the algorithm would be perfectly correct if it has backjumped to a decision trail

|6, 1, 2, |7, (any other choices not involved in the conflict, and literals propagated from 7 and them)

and then propagated -3 and got

|6, 1, 2, |7, (any other choices not involved in the conflict, and literals propagated from 7 and them), -3.

More generally, I am proposing that backjumping be defined not to go back to the most recent literal in C making it a unit clause (that is, 2), but to the most recent literal in the trail immediately before the last literal (-3) in C. That would be whatever is immediately before -3 in the trail, before the backjump, including 7, its propagations, and whatever other non-conflicting choices that happen to have been made.

Am I correct that this would be a better alternative that preserves work, or am I missing something?

\[1\] Fig. 6, trace of Example 7 if you are curious, but there is no need to go look as I think all the relevant information is here.

# Answer
> 2 votes
The intervening assignments between the current assignment and the backjump point might have been arrived at via considerable backtracking and backjumping themselves and it would be wasteful to repeat all that work. But in the context of a modern solver that work may not need to be repeated, because:

* Any conflicts that occurred during the intervening assignments should have produced conflict clauses that rule out those time-wasting bad assignments in the immediate future.
* Some solvers implement "phase saving" which remembers whether a variable was assigned true or false across backjumps (and restarts). So when DPLL chooses that variable again as a decision variable it will use the same true/false value, essentially picking up where it left off before the backjump.
* The intervening assignments may not be repeated in the same order after the backjump. Solvers have heuristics that decide which variable becomes the next decision variable. These heuristics usually give preference to variables recently involved in conflicts, which usually has the effect of shuffling the decision variable order after every conflict.

There is another reason to backjump past 7 and then assert -3 and that is because of the way two-watched-literals works. Two-watched-literals is a clever algorithm for noticing when clauses are made unit by an assignment. It uses a lazy data structure that does not need to be updated for every clause referenced by an assignment and more importantly does not need to be updated at all when backtracking or backjumping. You can assume every SAT solver that implements DPLL also uses this algorithm to track unit clauses.

But in order for the lazy data structure to work there are procedural rules that must be followed. One of them is that you must roll back decision variable assignments and their unit propagations as a group. So to use your example, if -3 were asserted after the 7 assignment instead of before it and the 7 assignment were ever rolled back, then the -3 assignment would be undone separate from the |6 1 2 assignments that caused it. This would leave clause C, \[-1 -2 -3\], as a unit clause but two-watched-literals would not detect it. DPLL search is now broken and the solver may be confused enough to later claim that it has a satisfying assignment when it doesn't. If -3 is asserted together with the other consequences of the 6 assignment, then all the implications of that assignment will be rolled back together as they must be.

---
Tags: satisfiability, sat-solvers, backtracking
---


# Question
Title: Prove Language Is Union of Fninitely Many Arithmetic Progressions
So, you see in the image the question and its answer (proof below the black line).

I get the entire proof until the last formula. It basically says that if length of a string is larger than number of states then one or more states need to be re-visited (at least one more times).
Formula for the L makes also perfect sense. It is union of strings like a^m when m \< j (explained above in the image) and a^m+(i-j)l (also explained in the picture).
I do not get the `P(h[L])=` formula. What is `h[L]`? And what is `P(h[L])`?

And one more question: How does this proof correspond to the question that {n:a^n ∈ L} is a union of finitely many arithmetic progressions?

Question: An **arithmetic progression** $\\{p+ qn : n = 0,1,2,...\\}$ for some $p,q ∈ N.$ Show that if $L \subseteq \\{a\\}^{\ast}$ is regular, then $\\{n : a^n \in L \\}$ is a union of finitely many arithmetic progressions.

Proof: Let $M = (K, \\{a\\}, δ, s, F)$ be a $DFA$ accepting L, and consider the set $K' \subseteq K$ of states which are reachable from the start state $s$. Since there is only one character in the alphabet, there is exactly one transition out of every state; thus, if we imagine reading the string $a^n$, we must pass through a series of states $q\_0,q\_1,...,q\_n,$ and if $n \> |K|$, then there exist $ 0\leq j \< i \leq n$ such that $q\_i = q\_j$. Effectively, then the reachable portion of $M$ consists of a chain of states, each with a transition to the next on the character $a$, followed by a loop of states. Thus, the strings accepted by the $DFA$ are, for any $m \< j$ such that $q\_m$ is finalm $a^m$, and for any $m \geq j$ such that $q\_m$ is final $a^{m+(j-i)l}$ for all $ l \geq 0.$
Thus $L = \bigcup \\{\\{a^m\\}:m \< j, q\_m \in F\\} \cup \bigcup \\{\\{a^{m+(j-i)l}:l \geq 0\\}: m \geq j, q\_m \in F\\}$, so
$$P(L) = \bigcup \\{\\{m+0l:l \geq 0\\}: m \< j, q\_m \in F\\} \cup \bigcup \\{\\{m+(j-i)l: l \geq 0\\}: m \geq j, q\_m \in F\\}$$

# Answer
> 6 votes
There is definitely a typo in the text; the sum in the final equation looks like $\bigcup \\{\\{m + 0l\\}\\} \cup \bigcup \\{\\{a^{m+(j-i)l}\\}\\}$, while $\bigcup \\{\\{m + 0l\\}\\} \cup \bigcup \\{\\{m+(j-i)l\\}\\}$ seems more logical.

I suggest to define $P$ in the task as:

> Show if $L \subseteq \\{a\\}^{\ast}$ is regular, then $P(L) = \\{n:a^n \in L\\}$ is a union of finitely many arithmetic progressions.

and make the final sentence the following:

> Thus $L = \bigcup \\{\\{a^m\\}:m \< j, q\_m \in F\\} \cup \bigcup \\{\\{a^{m+(j-i)l}:l \geq 0\\}: m \geq j, q\_m \in F\\}$, so
>
> $$P(L) = \bigcup \\{\\{m+0l:l \geq 0\\}: m \< j, q\_m \in F\\} \cup \bigcup \\{\\{m+(j-i)l: l \geq 0\\}: m \geq j, q\_m \in F\\}$$

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


# Question
Title: Cycles in hardness of ST-CON for the class NL
It seems to me that the problem of $s$, $t$ connectivity in a DAG should still be NL-Complete.

I am aware that ST-CON without the DAG restriction is complete for NL, so obviously the DAG restriction is still in NL, but I believe hardness follows as well:

For a turing machine that runs in space $s(n)$, its configuration graph is of size $2^{O(s(n))}$. Furthermore, this implies the time for an NL machine to solve any problem, if it halts at all, is also $2^{O(s(n))}$. Then you can blow up the configuration graph by including a counter for any possible time step a configuration is reached, resulting in a graph of size $2^{O(s(n))} \cdot 2^{O(s(n))} = 2^{O(s(n))}$. At this point the typical reduction to ST-CON can be used since the graph is the same size.

If this is true, then I do not understand why the result SL = L did not follow trivially from the formulation of SL. Namely, an undirected acyclic graph is a tree, and a simple maze algorithm can determine $s$, $t$ connectivity in log-space (and linear time!).

Another strange implication would be that the cyclic or non-cyclic versions of $s$, $t$ connectivity on directed or undirected graphs are equivalent for log-space computation. This implies a simple algorithm like the tree-based one for $s$, $t$ connectivity on a generic undirected graph.

# Answer
It turns out st-connectivity on a general digraph is log-space mapping reducible to st-connectivity on a DAG. Here is the reduction:

Given a directed graph $G$ of size $n$ and two vertices $s$ and $t$, first create a graph $G'$ by making $n$ copies of every vertex $u$ in $G$ as the new vertex $(u, i)$ in $G'$, where $i$ goes from $1$ to $n$ for the respective copies. Then, represent each edge $(u, v)$ in $G'$ by the transition $(u, i) \mapsto (v, i+1)$. Since any path from $s$ to $t$ is of length at most $n$, it then follows that a path from $s$ to $t$ exists in $G$ if and only if it exists in $G'$. Furthermore, since $i$ is always increasing in $(u, i)$, it is clear $G'$ is a DAG. Finally, the mapping can be computed in logarithmic space.

However, the approach does not work for undirected graphs, because cycles can occur in the layering technique. So although st-connectivity is easy on a tree, as described by my algorithm in the comments, undirected st-connectivity is not (directly) reducible to st-connectivity on a tree.

Therefore SL=L was not established until Reingold showed st-connectivity on an undirected graph is indeed solvable in log-space.
> 5 votes

---
Tags: algorithms, complexity-theory, reductions
---


# Question
Title: Probabilistic algorithm with two-sided error
I am currently studying probabilistic algorithms and came across three major complexity classes:

* BPP: worst-case polynomial time, two-sided error
* RP: worst-case polynomial time, one-sided error
* ZPP: average-case polynomial time, no error

At first I couldn't understand why one would use an algorithm that could err. I figured it does make sense in some cases though, like primality testing for RSA encryption. The algorithm used there has a one-sided error only, though.

Even after hours of thinking about it, I failed to think of an algorithm with two-sided error that actually makes sense and could be / is used in practice.

Any pointers would be greatly appreciated.

# Answer
> 5 votes
Monte Carlo methods are inherently *not* one-sided, though it's dubious whether they're usually two-sided. The general idea is that in order to estimate the expectation of a random variable $X$, we take the average of many samples of $X$.

For example, suppose that you're a petroleum company, and you're trying to decide where to look for oil. For every square in some grid you have some random variable $X\_i$, expressing the probability that there is oil in square $i$, that you can estimate using your (noisy) data. You have some threshold $\theta$ in mind, and will start drilling in every square $i$ for which $X\_i \geq \theta$. Using a Monte Carlo algorithm (say, simulating the geological history of the area), you can determine $X\_i$ up to some error $\epsilon$. This translates to a two-sided error algorithm.

You can also think of computation in general as having two-sided error. Hardware errors occur with extremely low probability, and they can affect the answer in every which way.

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


# Question
Title: Courses that give good insight on the nature of a Computer Science major?
I'm a business informatics student so I am taking introduction to computer science and computer programming, and so far I hate everything that has to do with this major aside from these 2 courses which I am really enjoying so far, so I am considering changing to a computer science and engineering major, but I want to make sure this is what I will enjoy before I make this change so I am researching some stuff relating to computer science online, one of which being discrete mathematics. Do you think discrete maths gives good insight on how CS is like? How about 'Theory of computation' and 'Intro to Artificial Intelligence'? Do you have any other recommendations for courses or subjects that DO give good insight on CS and do not have any course prerequisites so I can look into them and be able to follow? Thanks in advance to those who take the time to answer and help :)

# Answer
> 1 votes
Here are some thoughts about your suggestions for further study, plus one that you didn't mention.

**Discrete Mathematics**

This course should be part of the background for every computer scientist. The material is relevant for lots of areas we deal with and can be interesting and engaging whether or not one is going to concentrate on CS. That said, though, the subject matter won't necessarily give you an insight into what CS is really about unless it is specifically tailored to computer science applications (which it rarely is, in my experience).

**Theory of Computation**

A great choice, though it takes a bit of "mathematical maturity" to get through (meaning that you might find Discrete listed as a prerequisite). In one sense, this is the foundation for much of the rest of CS, since it asks "What things can and cannot be computed?" and often proceeds to answer this question by looking at increasingly more powerful models of computation, asking what kinds of problems these models can and cannot solve. Full disclosure: I'm a theorist and so find this area to be particularly beautiful.

**AI**

Well taught, this can turn out to be an eye-opening introduction to a lot of CS topics as well as being, in many people's opinion, just downright fascinating. Poorly taught, though, this can be little more than a specialized data structures course (still interesting, just not as much fun).

**Data Structures**

You didn't specify what your programming course covered, but this is a natural follow-on. Learning to program, you were exposed to what one might call the standard collections of algorithmic basics, like selection (if statements), loops, arrays, function calls, and (if you were lucky), recursion. A course in Data Structures goes on from there and usually is organized around the "canonical" structures used for organizing data, structures like lists, trees, stacks, hash tables, and the like. This is absolutely indispensable for any practicing computer scientist. At many schools, in fact, it's the next course to be taken after the first programming course.

So, what should you do next? All of your possibilities have their merits, but I'd advise a Data Structures course, for a couple of reasons. First, if you take it and hate it (assuming that your reaction isn't just due to a lousy teacher or a poorly-designed course), then CS is probably not the way you want to continue and it'll be good to find that out early. If, on the other hand, you take it and walk out with the reaction "that was fun", then you'll not only have shown you probably have an aptitude for all the rest that will follow, but at most schools, you'll have placed yourself at the right point in the CS curriculum to continue.

Best of luck.

---
Tags: education
---


title: Computing vector load and stores

text:
# Question
Title: Computing vector load and stores
If $a,b,c,y$ are all scalar doubles, then $y = a\cdot b$ would result in 16 bytes from loading $a,b$ and 8 bytes for storing $y$, a total of 24 bytes transferred. Likewise, $y = a\cdot b + c$ results in 24 bytes from loading $a,b,c$ and 8 for storing $y$ hence 32 total bytes transferred. Now let $\boldsymbol{X},\boldsymbol{Y},\boldsymbol{Z}$ be vectors of size N and $w$ be a scalar. How many total bytes transferred (loads/stores) would the following operations take

1) $\boldsymbol{Z} = w\boldsymbol{X} + \boldsymbol{Y}$

2) $w = \boldsymbol{X}\cdot\boldsymbol{Y}$

My guess would be 4\*N\*8 and (2\*N+1)\*8 respectively for these reasons:

1) I load two vectors of size N, load a scalar N times, and store a vector of size N.

2) I load two vectors of size N, and do a reduction that stores a single scalar.

If what I have is incorrect, what should the answers be?

# Answer
In formulating an answer it would be really helpful to understand *why* you are trying to calculate this. If it's a theoretical exercise then your reasoning may hold however if it's for any real application, it fails to take into account compiler optimisation and the fact that values may be in L1 cache or registers rather than being loaded from L2 or other storage.

It also overlooks the fact that many modern, optimised matrix libraries would vectorise the vector operations using GPU or even the CPU's multiple cores which would make this type of calculation far from simple.

Any answer would depend on what you are assuming about your CPU architecture and it's capabilities so there's no *right* answer per-se. Also, even assuming a naive CPU architecture with a single accumulator, you didn't specify the data type of the vectors
> 1 votes

---
Tags: data-structures, memory-access
---


# Question
Title: If one shows that UNIQUE k-SAT is in P, does it imply P=NP?
Valiant & Vazirani proved SAT is reducible to UNIQUE SAT under randomized probabilistic reductions in polynomial time. Calabro *et al*. showed that UNIQUE k-SAT is as hard as k-SAT. Now the question is, if someone shows that UNIQUE k-SAT is in P, does it imply P=NP?

**References**

1. L. G. Valiant and V. V. Vazirani, "NP is as easy as detecting unique solutions." *Theoretical Computer Science* 47:85–93, 1986. (PDF on ScienceDirect.)
2. C. Calabro, R. Impagliazzo, V. Kabanets and R. Paturi, "The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs". *Journal of Computer and System Sciences* 74(3):386–393, 2008. (PDF at ACM Digital Library; free PDF.)

# Answer
> 12 votes
This is still an open question; **UP** is not known to be equivalent to **NP**. In the paper "NP Might Not Be As Easy As Detecting Unique Solutions," Beigel, Burhman and Fortnow construct an oracle under which **P** contains **UP** but **P** is still not equivalent to **NP**.

---
Tags: complexity-theory, satisfiability, p-vs-np
---


# Question
Title: Prove Undecidability: TM M enters each of its states on Input W?
Consider the following problem: given a Turing Machine $M$ and an input string $w$, does $M$ enter each of its states during its computation on input $w$?

How to prove that the problem is undecidable?

I was trying to prove undecidability by Rice's theorem which states that languages having non-trivial property are undecidable. But how can I adjust the problem to the theorem?

# Answer
> 2 votes
**Hint.** We can assume that a Turing machine has exactly one halting state. If a TM visits all of its states, it certainly visits the halting state. Now figure out a way to modify Turing machines so that, if they do halt, they cycle through all their states just before doing so. This gives you a class of TMs that visit every state if and only if they halt.

---
Tags: computability, turing-machines, undecidability, rice-theorem
---


# Question
Title: Chandy/Misra dining philosophers solution
So based on the Chandy/Misra section in this Wikipedia article we've got 5 philosophers numbered P1-P5.

Based on this quote:

> For every pair of philosophers contending for a resource, create a fork and give it to the philosopher with the lower ID (n for agent Pn). Each fork can either be dirty or clean. Initially, all forks are dirty
>
> When a philosopher with a fork receives a request message, he keeps the fork if it is clean, but gives it up when it is dirty. If he sends the fork over, he cleans the fork before doing so.

So with the knowledge that all forks are initially dirty, regard the following quote and the image underneath it.

> For every pair of Swansons, give the fork to the guy with the smaller id.

My question is if P3 now requests a second fork from his neighbor P4, will P4 give up his single fork beacause it was dirty, even though he just picked it up?

# Answer
> 0 votes
Yes. Whenever a philosopher asks for a fork that is dirty, the philosopher who currently has that fork cleans it and gives it to the person who asked for it.

So, in the initial position, 1 has two dirty forks and can eat, 2, 3 and 4 have one dirty fork each and 5 has no forks at all. If 3 requests a fork from 4, 4 cleans it and gives it to him. This leads to the state where 1 has two dirty forks and can eat, 2 has one dirty fork, 3 has one clean fork and one dirty fork and can eat, and 4 and 5 have no fork.

---
Tags: algorithms, operating-systems, concurrency, synchronization
---


# Question
Title: algoritm to convert a monoid into an automaton
In literature, is there an algoritm to convert a monoid into an atomaton?

I am looking for references/applications.

# Answer
**Short answer**. See the Cayley graph of the monoid as an automaton.

**Details**. Let $L$ be a language recognised by a finite monoid $M$. Then there is a morphism $\varphi:A^\* \rightarrow M$ and a subset $P$ of $M$ such that $L = \varphi^{-1}(P)$. Take the right representation of $A$ on $M$ defined by $s \cdot a = s\varphi(a)$. This defines a deterministic automaton $\mathcal{A} = (M, A, \cdot, 1, P)$. Now, a word $u$ is accepted by $\mathcal{A}$ if and only if $1 \cdot u \in P$. Since $1 \cdot u = \varphi(u)$, this condition means $\varphi(u) \in P$ or $u \in \varphi^{-1}(P)$. Since $L = \varphi^{-1}(P)$, we conclude that $\mathcal{A}$ recognises $L$.
> 3 votes

---
Tags: formal-languages, group-theory
---


# Question
Title: What is the difference between Strict 2Phase Locking and 2Phase Locking?
I have read some notes about the two but yet still confused about why there is a need for the strict 2phase locking. Based on some slides,

Two Phase Locking and Strict Two Phase Locking

They have a single difference which is :

1. If transaction T releases any lock, it can acquire no new locks. \<- 2PL
2. Hold all locks until end of transaction. \<- S2PL

I will like a practical example of a Transaction in both strict and normal.Highlighting the differences.

# Answer
There are mainly two reasons for adopting Strict 2PL rather than Basic 2PL, explained in \[1\].

* The first reason is about the time when a 2PL scheduler can release some (read/write) lock owned by some transaction on some data item.
* A second reason for the scheduler to keep a transaction’s locks until it ends, and specifically until *after* the DM processes the transaction’s Commit or Abort, is to guarantee a *strict* execution. Strict executions are recoverable and avoid cascading aborts (ACA).

---

\[1\] Chapter 3 "Two Phase Locking" in the Book "Concurrency Control and Recovery in Database Systems"; Page 59. By Bernstein et al., 1987.
> 1 votes

---
Tags: database-theory
---


# Question
Title: Time complexity of a classical version of Shor's algorithm
I'm sorry if this question seems too naive. I've read the Shor's algorithm of factoring big number using quantum computer on Wikipedia. It says,the key step is to find the cycle of the function defined on positive integers:f(x)=a^x mod N, where a and N are positive integer,and N is very large.

What I would like to do is to analyze the time complexity of this key step using a classical computer.I tried the following: Wikipedia's page on modular exponentiation, I see f(x\_0) takes O(N),(or less),and let x\_0 = 1 to N takes N\*O(N)=O(N^2),which is enough to find the cycle of f(x). This lead to the conclusion that the whole factoring algorithm is in polynomial time on a classical computer,which is not the case as far as I know.

So I must be wrong somewhere.Thanks for any help.

# Answer
When we say that an algorithm runs in polynomial time, we mean that there is a constant $k$ such that the algorithm runs in time $O(n^k)$, where $n$ is the length of the input as a string. When the modulus $N$ is part of the input, it's specified in binary (or any number system other than unary) so the length of that part of the input is only about $\log N$. Thus, running in time $O(N^2)$ corresponds to running in time $(2^{\log N})^2$, which is not a polynomial in the *length* of the input.
> 3 votes

# Answer
We usually want our algorithms to run in polynomial time in the *length* of the input, which is roughly $\log N$. Imagine that $N$ is a 512-bit integer. You would like the algorithm to run in time polynomial in 512 rather than $2^{512}$.
> 1 votes

---
Tags: algorithm-analysis
---


# Question
Title: Paxos: Responding to Reordered Prepare Requests
In the paper, Paxos Made Simple, a proposer asks an acceptor to respond to a prepare request with:

> A promise never to again accept a proposal numbered less than n, and the proposal with the highest number less than n that it has accepted.

Therefore:

> \[An acceptor\] can receive two kinds of requests from proposers: prepare requests and accept requests. An acceptor can ignore any request without compromising safety. So, we need to say only when it is allowed to respond to a request. It can always respond to a prepare request. It can respond to an accept request, accepting the proposal, iff it has not promised not to.

Next, Lamport offers this optimization:

> Suppose an acceptor receives a prepare request numbered $n$, but it has already responded to a prepare request numbered greater than $n$, thereby promising not to accept any new proposal numbered $n$. There is then no reason for the acceptor to respond to the new prepare request, since it will not accept the proposal numbered n that the proposer wants to issue. So we have the acceptor ignore such a prepare request.

Suppose an acceptor receives a prepare request numbered $n$, but it has responded to a prepare request numbered $n + 1$ and accepted the proposed value (the prepare request for proposal $n$ was delayed arbitrarily by the network). The acceptor has thus promised never to accept a proposal numbered less than $n + 1$. However, we know that:

> an acceptor can always respond to a prepare request.

Therefore, the acceptor can respond with a promise never to accept a proposal numbered less than $n$ since it has already made a promise never to accept a proposal numbered less than $n + 1$, however it cannot respond to the prepare request for proposal number $n$ with the proposal $n + 1$ because it must respond with:

> The proposal with the highest number **less than $n$** that it has accepted.

Since $n + 1 \> n$ it can respond with no proposal. This would enable both the proposer of proposal number $n$ to choose a value, and the proposer of proposal number $n + 1$ to choose a value. However, even in the case where the proposer of $n$ sent their accept request before the proposer of $n + 1$, the accept request would be ignored because a majority has promised not to accept a proposal numbered less than $n + 1$. Thus, safety is still guaranteed. Is this correct?

# Answer
> 3 votes
Correct. Another way to think about Paxos is as a two step process:

1. Gaining permission to propose a value
2. Actually proposing a value

The act of successfully gaining permission from a majority of peers to propose a value explicitly precludes the possibility of any previous proposal from being accepted by a majority of peers.

---
Tags: distributed-systems
---


# Question
Title: Stateless pseudorandom/hash algorithm for ℤⁿ → [0,1)
There's a problem which I had on a number of unrelated occasions which I usually work around in some way or another. Deep inside, though, it bothers me that I haven't ever found a “proper” solution to this:

> Given an *n*-tuple of integers, how do I derive a stateless pseudorandom number / hash value in the half-open interval \[0,1)?

The usual “solution” people use in this situation is to multiply the parameters by some large primes, or bit-shift them, or do any other complex calculation which produces a result that is “random enough” for the given purpose. I guess these algorithms have been cargo-culted over a long time, maybe from a PRNG implementation.

Instead of copying one of the circulating code snippets, I'd like to really understand what's going on here. Is there an algorithm or a set of algorithms which should typically be used in this kind of situation, and if so, what's the proper way to choose the constants?

# Answer
> 4 votes
Every hash function is stateless; that's part of the definition of what it means to be a hash function.

A simple approach is to take a representation of the input in binary, using any standard encoding for the integers and for $n$-vectors of integers, and then hash the result using your favorite hash function. The output will be a binary string. Treat it as the binary representation of a number in the range $\[0,1)$ (put a decimal point before the start of it, and interpret it in base 2). That's your output.

Then, choose a suitable hash function for hashing binary strings. If you need it for cryptographic purposes, you could use SHA256. If you need it for non-cryptographic purposes, there are many standard, fast hash functions; choose one that meets your requirements. Since you didn't state any precise requirements in the question, we have no basis to select among any of the standard solutions.

---
Tags: hash, randomness
---