# Question
Title: Is there a faster solution for the Google Code Jam Great Wall Problem
Consider the following Google Code Jam round 1C question:

The Great Wall of China starts out as an infinite line, where the height at all locations is $0$.

Some number of tribes $N$, $N \le 1000$, will attack the wall the wall according to the following parameters - a start day, $D$, a start strength $S$, a start west-coordinate, $W$, and a start east-coordinate, $E$. This first attack occurs on day $D$, on range $\[W,E\]$, at strength $S$. If there is any portion of the Great Wall within $\[W,E\]$ that has height $\< S$, the attack is successful, and at the end of the day, the wall will be built up such that any segment of it within $\[W,E\]$ of height $\< S$ would then be at height $S$ (or greater, if some other attack that day hit upon the same segment with strength $S' \> S$)

Each tribe will perform up to $1000$ attacks before retreating, and each attack will be determined iteratively from the one before it. Every tribe has some $\delta\_D$, $\delta\_X$, and $\delta\_S$ that determines their sequence of attacks: The will wait $\delta\_D \ge 1$ days between attacks, they will move their attack range $\delta\_X$ units for each attack (negative = west, positive = east), though the size of the range will stay the same, and their strength will also increase/decrease by a constant value after each attack.

The goal of the problem is, given a complete description of the attacking tribes, determine how many of their attacks will be successful.

I managed to code a solution that does work, running in about 20 seconds: I believe the solution I implemented takes $O(A\log A + (A+X)\log X)$ time, where $A =$ the total number of attacks in a simulation (max $1000000$), and $X =$ the total number of unique edge points on attack ranges (max $2000000$).

At a high level, my solution:

* Reads in all the Tribe information
* Calculates all the unique $X$-coordinates for attack ranges - $O(A)$
* Represents the Wall as a lazily-updated binary tree over the $X$ ranges that tracks minimum height values. A leaf is the span of two $X$ coordinates with nothing in-between, and all parent nodes represent the continuous interval covered by their children. - $O(X \log X)$
* Generates all the Attacks every Tribe will perform, and sorts them by day - $O(A \log A)$
* For each attack, see if it would be successful ($\log X$ query time). When the day changes, loop through all unprocessed successful attacks and update the wall accordingly ($\log X$ update time for each attack). - $O(A\log X)$

My question is this: Is there a way to do better than $O(A\log A + (A+X)\log X)$? Perhaps, is there some strategic way to take advantage of the linear nature of Tribes' successive attacks? 20 seconds feels too long for an intended solution (although Java might be to blame for that).

# Answer
The obvious room for improvement is this step:

> Generates all the Attacks every Tribe will perform, and sorts them by day - $O(A\log A)$

We know that the tribes will attack from a particular day, in regular intervals. That means we should be essentially merging lots of pre-sorted lists. Also the problem statement tells us that there will never be more than 1,000 tribes (i.e. 1,000 lists to merge); a tiny number compared with the 1,000,000 maximum attacks! Depending on your implementation's relative timings, switching this could cut the processing time in half.

That's really all I can suggest for optimising the theoretical complexity, but I have no proof that it would be optimal after this change.

---

I gave the puzzle a go myself, but I used a much dumber representation of the wall: a binary search tree (C++'s `std::map` to be precise) storing locations where the wall's height changes. With this, I was able to add and removed nodes as required (i.e. if a complicated section was subject to a large, overwhelming attack, or multiple attacks of the same strength touched, the number of nodes would reduce significantly). This solved the large input in 3.9 seconds (on my mid-spec development laptop). I suspect there are several reasons for the improvement:

* As you pointed out, boxing and unboxing can get expensive, but C++'s template-based containers avoid this entirely.
* While the wall representation I used is theoretically worse, in the vast majority of cases being able to dynamically reduce the number of nodes made it super-fast (most test cases maxed-out at under 1k nodes, and all but 2 were under 10k). In fact, the only case which took any significant time was #7, which seems to have been testing lots of non-intersecting ranges.
* ~~I used no pre-processing (stages are determined by keeping track of when each tribe will next attack, and searching for the joint-lowest each turn). Again this is theoretically worse, but for the majority of cases I suspect the lower overhead means it was faster (I'll test this and get back to you).~~ **Update**: I added a priority queue for attacks, similar to the method described above (although instead of creating the large array I calculated it on-the-fly) and saw the time decrease to 3.0 seconds for the large input.

In short, while I think your algorithm is near-optimal in the general case, there are several ways you could speed it up *for typical inputs*.
> 2 votes

# Answer
*The following was removed from the question, as it is an answer.*

Looking over other discussions and successful solutions seems to indicate that the solution I've described is pretty much the expected algorithm. The slow-down in my solution is possibly just due to lazy use of auto-boxing and a pointer-based tree structure, rather than an array-based one - so I suspect that, if a solution does exist, it's probably not a whole lot better than what's here.

The solution can be found here. It's very much the same as what I have posted here; so I am much more inclined to believe that a more efficient solution does not exist.
> 1 votes

---
Tags: algorithms, data-structures, binary-trees
---


title: Deleted data remains on a disk until?

text:
# Question
Title: Deleted data remains on a disk until?
I am little bit confused between the two answers below. What is the exact answer of this question?

My query is, "Deleted data remains on a disk until...?"

1. The data is overwritten;
2. The recycle bin is emptied.

I have searched it over internet and books, but I have found various answers. Please explain to me. Thank you in advance.

# Answer
> 2 votes
It depends on the file system used and preferences provided, but in the most common case - deleted data is marked as deleted (dirty) and is used when some new data is to be written. Priority of usage of dirty block earlier than empty depends on system preferences.

The recycle bin is different case - until emptied there is guarantee to recover files, so it is not deleted per se.
After recycle bin is emptied file is deleted (so flagged as deleted and then based on preferences stays there or is physically deleted).

---
Tags: operating-systems, memory-hardware, filesystems
---


# Question
Title: Blank tape halting problem vs. Emptiness problem ($H_0$ vs. $E_{TM}$)
I have difficulties to differentiate the $H\_0$ from the $E\_{TM}$ problem.

What exactly means $L(M)= \emptyset $? Is it dffierent from $input~ \varepsilon$ or is $L(M)= \emptyset \leftrightarrow input~ \varepsilon$

**Emptiness problem:**
$E\_{TM} = \\{\langle M \rangle | ~M~ is~ a~ Turing~ machine~ and~ L(M)= \emptyset \\}$
$E\_{TM}$ is undecidable
$E\_{TM}$ is recognizable but not co-turing-recognizable
$E\_{TM}$ is not recognizable but co-turing-recognizable

**Blank tape halting problem:**
$H\_0 = \\{\langle M \rangle ~ |~ M~ is~ a~ Turing~ Machine~ that~ halts~ on~ input~ \varepsilon ~\\}$
$H\_0$ is undecidable
$H\_0$ is recognizable but not co-turing-recognizable

any help is greatly appreciated

# Answer
Yes, they are different. $L(M)$ is the set of all inputs accepted by a Turing machine, so $E\_{TM}$ asks if a Turing machine doesn't accept any inputs. $H\_0$ asks whether a particular input (the empty string) is accepted. BTW, $E\_{TM}$ should be co-Turing-recognizable, but not Turing-recognizable.
> 5 votes

---
Tags: computability, turing-machines, halting-problem
---


# Question
Title: Complexity of GF(2) and applications to cryptography
If I have a system of N polynomial equations with N unknowns in GF(2):

* What are some good methods to solve them?
* What's the highest value of N that can be reasonable solved?

Now, my root interest isn't GF, it's crypto. Here's my reasoning:

1. Any function from a n-dimensional binary vector to {0,1} can be represented as a GF(2) polynomial function of n variables.
2. Thus, for instance, any cipher from (Plaintext, Key) to Ciphertext can be represented as a series of equations (one for each bit in the ciphertext), each a GF(2) polynomial of (p-bits + k-bits) variables.
3. Thus, if we know P and C, and we can solve systems of GF(2) equations, we can determine K.

# Answer
The (meta) algorithm you're looking for is the Gröbner basis algorithm. In the last decade, the approach that you mention, called *algebraic attacks*, has gained momentum in the cryptological community. One person who has been developing efficient Gröbner basis algorithms in the context of cryptography is Faugère. He has some links to relevant papers on his web page, including applications.

Since SAT can also be written as a (small) system of polynomial equations, you shouldn't expect a general algorithm to work always, or even on average. The hope is that *some* systems of polynomial equations are easier. You have to find these "easy" systems in order to apply this method in cryptology.
> 5 votes

# Answer
Gröbner bases are one approach, but you should also explore SAT solvers. For some problem instances, SAT solvers seem to be more effective. There's a straightforward translation of equations over GF(2) to SAT instances.

If you want to try out various SAT solvers, MiniSAT is a good starting point; it is a solid SAT solver that is pretty good. You might be especially intersted in CryptoMiniSAT, which is based upon MiniSAT but is extended to be especially useful for cryptographic problems. In particular, it was extended to be more effective at reasoning about XOR operations, which are common in cryptography (XOR corresponds to addition in GF(2)), though you may have to set a special configuration parameter to enable this support fully. STP is also a convenient tool for this, as it contains a built-in pre-processing that applies Gaussian elimination over GF(2), which can be convenient for some problem instances.

Finally, you could learn about linearization (converting non-linear equations into linear ones, over a larger set of variables) and re-linearization (applying this idea multiple times). This can sometimes be effective if you have a highly over-constrained set of equations over GF(2).

See also http://www.cryptosystem.net/aes/tools.html (but I make no guarantees whether anything there is accurate or useful).
> 2 votes

# Answer
Here is a good article that answer those questions.

> What are some software packages or libraries that implement this?
> What are some good methods to solve them?

Allan Steel in Magma, cubic Gaussian elimination implemented by **Victor Shoup**. And the two methods from the article I suggested.

> What's the highest value of N that can be reasonable solved?

Base on the references I gave you, a cubic matrix with 100,000 rows would take hours to solve. You can look on the values from the article below.

```
Matrix Dimension        Cubic PLE        Algorithm 2
-----------------------------------------------------------------
10, 000 × 10, 000       1.478s              0.880s
16, 384 × 16, 384       5.756s              3.570s
20, 000 × 20, 000       8.712s              5.678s
32, 000 × 32, 000       29.705s             24.240s

```
> 1 votes

---
Tags: algorithms
---


# Question
Title: Identifying system events affecting timing behavior of an application
**Q:** What are those events (system level and architecture level) that can cause an application to take longer to terminate and complete the job?

My question is purely in the context of Worst Case Execution Time (WCET) analysis.

I have gathered a short list of events, which I think are the contributors to WCET of an application, by utilizing some knowledge about computer-architecture:

* A wrong branch prediction
* Cache misses
* Pipleline stalls
* Fetch related delays
* . . .

I would like to enrich this list both in breadth and length. So any addition to the list of such events or the details of how any particular event causes a delay is most welcomed.

P.S. If my question if not well formulated, please do help me to improve.

# Answer
You forgot the most obvious factor: the input of the program. The time taken by a program heavily depends on the input unless it does not have any input or the input comes from a small fixed set.

Other factors can be classified into two classes: 1) Internal factors and 2) External factors.

Internal factors:
1) Input
2) Waiting for I/O
3) Waiting for System resources like memory/semaphores etc.
4) How effectively memory is cached in CPU (may be different for different runs, what you have termed as cache misses.)
5) Disruptions in instruction pipeline
6) Interactive events
7) If the process needs to swap in/out some pages to swap area
8) If the process uses other hardware such as graphics card/audio/network
9) Hardware interrupts from graphics card/audio/network
10) Clock interrupts
11) Scheduler running
12) If the process is multi-threaded, then delays because of thread switching
13) If the process is multi-core and you need to share data between core, delay depends on the architecture of the CPU

External factors:
1) Multiprocessing (the biggest culprit)
2) Priority of the process
3) Context switching
4) Operating System preemptions
5) Hardware errors and service interruptions (of course)
6) Communication with other processes
7) Communication with other processes in other machies
8) Input that is not readily available, (it is available as a stream)

We need to have a good guess of running time of a process for majority of scheduling algorithms and for real-time systems. But a perfect calculation is simply impossible in real cases. The usual practice is to run the process for typical (or typically worse) case input many times, make a guess and then over estimate it. This is done even in real-time system, if I understand correctly. In quite a few real-time systems the running process quite arbitrarily demands a guarantee of what it thinks is the over-estimated time it will take to finish the computation.
> 3 votes

# Answer
I'd agree that your list includes many items that can cause execution to lengthen. But those are all directly related to the execution of the application code itself.

Also consider events which have nothing directly to do with the application itself such as:

Context Switching: IF another process is allowed to preempt your application, there is a cost to saving and restoring your process's state, not to mention the unknown time that the other process will run. Your scheduling algorithm will determine if this is a cost and steps that can be taken to control it.

Device interrupts - usually the process being interrupted is still considered the current process, but system level interrupt handling code is the code running. The current process waits until the interrupt is handled and a Return from Interrupt instruction restores the process state and process instructions resume. Interrupts can occur at "random" intervals and it is difficult to accurately predict the effect on any given run of a process. It's possible to measure average numbers of interrupts and interrupt stack time on some systems and use those averages. Time spent in individual interrupt routines is largely dependent upon the programmers who wrote the routines. Best practice is to do the minimum required processing in the interrupt routine and provide some mechanism for less critical processing to be done later at a lower priority. For VERY critically time sensitive code, interrupts can be blocked on most systems (by privileged code), but again best practice is to limit this code to the minimum.

Interval Clock Interrupts - These are more predictable than device interrupts but also stop the flow of your program to perform system level activities (updating system clocks, check scheduling queues, checking timer events, etc.).

Hardware errors - These are events that are unpredictable and cause interrupts that behave similar to device interrupts. Error interrupts are not always able to be blocked, but if these are occurring it is usually possible to eliminate them by repairing the hardware.
> 2 votes

---
Tags: time-complexity, runtime-analysis, computer-architecture, cpu-cache, cpu-pipelines
---


# Question
Title: How and which component of an Operating System is responsible for the transition of a process from the blocked state to the ready queue?
A process in an Operating System is considered to occupy several states and a process transitions between these states. A scheduler is responsible for assigning CPU time to a process. However, a process that is performing an Input Output Operation and has gone into the blocked state must transition to the ready state or the ready queue to be more precise to be considered for scheduling by the scheduler. Which component of the operating system handles this transition? And does this transition require any CPU time for operation?

# Answer
> 3 votes
When an I/O is started, it will typically have an I/O request structure associated with it that includes items like the process ID that the I/O belonged to. When the I/O completes the device driver will typically fork into an OS level I/O subsystem in the OS which will queue the IO request packet notification to the process and move the process to a computable queue. (this may vary a little from one OS to another). The process then waits for it's turn to become computable.

And yes, anything that executes code requires CPU time... though this is considered "interrupt time" rather than user time.

---
Tags: operating-systems, scheduling, process-scheduling
---


# Question
Title: Finding a small Moore machine that checks the last four bits
I am looking for a Moore finite state machine that returns true if and only if the last 4 bits (the input is of bits) are 0011 or 0101, the FSM can return any value at the first 4 bits (yes, even at the 4th).

The issue is that I was asked for a 7 conditions (vertexes) limit, and despite my efforts could not create one, my questions are the following :

1. Is there a FSM that solve this at 7 conditions (7 vertexes)? If there is than what is it and if not how can I prove there isn't?
2. Is there any type of 'algorithm' to approach this? I can easily well define one if we can use as much conditions as we wish (16 for our case) but what way other than intuition can lead me to reducing to 7 conditions?

# Answer
Since you have been given an upper limit to number of states, the best way to go about solving this problem is to get a correct solution first independent of number of states and then minimize the automata. Every moore automata has a canonical unique automata of minimum number of states (meaning all minimum state automata are equivalent).

As the solution is following and you cannot minimize the moore automata any further, you can declare that you cannot solve the problem with 7 states:

By the way, minimization of moore automata is similar to minimization of deterministic finite automata. We need to find equivalent states and merge them. Refer DFA Minimization.
> 1 votes

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


title: complexity of modal logic axioms

text:
# Question
Title: complexity of modal logic axioms
I am writing a paper in which I want to include complexity results for different modal logics and possibly add a reference to a specific paper.

At the moment I have the following:

K- no restrictions on the frame, NPComplete

T- reflexive, NPComplete

K4- transitive, PSpaceComplete

S4 and S4.3 also PSpaceComplete

S5- symmetric, transitive and reflexive, NPComplete.

**I am not able to find any results regarding complexity of the following axioms for modal logic:**

D- serial

KB- symmetric

B- reflexive, symmetric

**The above 3 modal logics are important for me and I really need the complexity results with a specific paper. If anyone could help me out here it would be great thanks.**

# Answer
> 3 votes
You might find interesting some of the results in On the Complexity of Fragments of Modal Logics by Linh Anh Nguyen (in Advances in Modal Logic, 2004: 249-268). A version of the paper is available in the home page of Nyugen.

And probably you are already familiar with A guide to completeness and complexity of modal logics by Joseph Y. Halpern and Yoram Moses (in Artificial Intelligence 54, 1992, pp. 319-379). A version of the paper similar to the published version is available in postscript and pdf in the home page of Halpern.

---
Tags: complexity-theory, logic, space-complexity, propositional-logic, modal-logic
---


# Question
Title: How to prove that a grammar is unambiguous?
My problem is how can I prove that a grammar is unambiguous? I have the following grammar: $$S → statement ∣ \mbox{if } expression \mbox{ then } S ∣ \mbox{if } expression \mbox{ then } S \mbox{ else } S$$

and make this to an unambiguous grammar, I think its correct:

* $ S → S\_1 ∣ S\_2 $
* $S\_1 → \mbox{if } expression \mbox{ then } S ∣ \mbox{if } expression \mbox{ then } S\_2 \mbox{ else } S\_1$
* $S\_2 → \mbox{if } expression \mbox{ then } S\_2 \mbox{ else } S\_2 ∣ statement$

I know that a unambiguous grammar has one parse tree for every term.

# Answer
There is (at least) one way to prove unambiguity of a grammar $G = (N,T,\delta,S)$ for language $L$. It consists of two steps:

1. Prove $L \subseteq \mathcal{L}(G)$.
2. Prove $\[z^n\]S\_G(z) = |L\_n|$.

The first step is pretty clear: show that the grammar generates (at least) the words you want, that is correctness.

The second step shows that $G$ has as many syntax trees for words of length $n$ as $L$ has words of length $n$ -- with 1. this implies unambiguity. It uses the structure function of $G$ which goes back to Chomsky and Schützenberger \[1\], namely

$\qquad \displaystyle S\_G(z) = \sum\_{n=0}^\infty t\_nz^n$

with $t\_n = \[z^n\]S\_G(z)$ the number of syntax trees $G$ has for words of length $n$. Of course you need to have $|L\_n|$ for this to work.

The nice thing is that $S\_G$ is (usually) easy to obtain for context-free languages, although finding a closed form for $t\_n$ can be difficult. Transform $G$ into an equation system of functions with one variable per nonterminal:

$\qquad \displaystyle \left\[ A(z) = \sum\limits\_{(A, a\_0 \dots a\_k) \in \delta} \ \prod\limits\_{i=0}^{k} \ \tau(a\_i)\ : A \in N \right\] \text{ with } \tau(a) = \begin{cases} a(z) &, a \in N \\ z &, a \in T \\ \end{cases}.$

This may look daunting but is really only a syntactical transformation as will become clear in the example. The idea is that generated terminal symbols are counted in the exponent of $z$ and because the system has the same form as $G$, $z^n$ occurs as often in the sum as $n$ terminals can be generated by $G$. Check Kuich \[2\] for details.

Solving this equation system (computer algebra!) yields $S(z) = S\_G(z)$; now you "only" have to pull the coefficient (in closed, general form). The TCS Cheat Sheet and computer algebra can often do so.

---

### Example

Consider the simple grammar $G$ with rules

$\qquad \displaystyle S \to aSa \mid bSb \mid \varepsilon$.

It is clear that $\mathcal{L}(G) = \\{ww^R \mid w \in \\{a,b\\}^\*\\}$ (step 1, proof by induction). There are $2^{\frac{n}{2}}$ palindromes of length $n$ if $n$ is even, $0$ otherwise.

Setting up the equation system yields

$\qquad \displaystyle S(z) = 2z^2S(z) + 1$

whose solution is

$\qquad \displaystyle S\_G(z) = \frac{1}{1-2z^2}$.

The coefficients of $S\_G$ coincide with the numbers of palindromes, so $G$ is unambiguous.

---

1. The Algebraic Theory of Context-Free Languages by Chomsky, Schützenberger (1963)
2. On the entropy of context-free languages by Kuich (1970)
> 27 votes

# Answer
For some grammars, a proof by induction (over word length) is possible.

---

Consider for example a grammar $G$ over $\Sigma = \\{a,b\\}$ given by the following rules:

$\qquad \displaystyle S \to aSa \mid bSb \mid \varepsilon$

All words of length $\leq 1$ in $L(G)$ -- there's only $\varepsilon$ -- have only one left-derivation.

Assume that all words of length $\leq n$ for some $n \in \mathbb{N}$ have only one left-derivation.

Now consider arbitrary $w = w\_1 w' w\_n \in L(G) \cap \Sigma^n$ for some $n \> 0$. Clearly, $w\_1 \in \Sigma$. If $w\_1 = a$, we know that the first rule in every left-derivation has to be $S \to aSa$; if $w\_1 = b$, it has to be $S \to bSb$. This covers all cases. By induction hypothesis, we know that there is exactly one left-derivation for $w'$. In combination, we conclude that there is exactly one left-derivation for $w$ as well.

---

This becomes harder if

* there are multiple non-terminals,
* the grammar is not linear, and/or
* the grammar is left-recursive.

It may help to strengthen the claim to all sentential forms (if the grammar has no unproductive non-terminals) and "root" non-terminals.

I *think* the conversion to Greibach normal form maintains (un)ambiguity, to applying this step first may take care of left-recursion nicely.

The key is to identify one feature of every word that fixes (at least) *one* derivation step. The rest follows inductively.
> 7 votes

# Answer
This is a good question, but some Googling would have told you that there is no general method for deciding ambiguity, so you need to make your question more specific.
> 6 votes

# Answer
Basically, it's a child generation problem. Start with the first expression, and generate it's children .... Keep doing it recursively (DFS), and after quite a few iterations, see if you can generate the same expanded expression from two different children. If you are able to do that, it's ambiguous. There is no way to determine the running time of this algorithm though. Assume it's safe, after maybe generating 30 levels of children :) (Of course it could bomb on the 31st)
> 3 votes

---
Tags: context-free, formal-grammars, proof-techniques, ambiguity
---


title: Compare Complexity of Graph Algorithm

text:
# Question
Title: Compare Complexity of Graph Algorithm
Assume I know that there is an algorithm of complexity
$ \mathcal{O}( log ( \vert V \vert^2 \vert E \vert ) ) $ for a Graph $G(E,V)$.

How do I compare this for example to the complexity of
$ \mathcal{O}( \vert V \vert^2 + \vert E \vert ) $ or other complexity algorithms on $G$.

There has to be a connection between $\vert E \vert$ and $\vert V \vert $ if I am right which is needed to solve this. But the only thing I found is $max .\vert E \vert = \frac{\vert V \vert }{2}(\vert V \vert -1)$, what does not help here and in many other cases.

Or should I just assume $max .\vert E \vert = \frac{\vert V \vert }{2}(\vert V \vert -1)$ and $min.\vert E \vert = \vert V \vert -1$ ?
Btw. must a vertex be connected via an edge to the graph per definition?

# Answer
> 1 votes
First of all $\min (|E|) = 0$ since the graph can be disconnected. $\min(|E|) = |V| - 1$, is true only for connected graphs. Whether a vertex is needed to be connected to the graph depends on the problem being considered. In general, a vertex can be isolated. So, in general, $0 \leq |E| \leq {{|V|}\choose{2}}$, if the graph is not a multi-graph. If the graph is a multi-graph then there is no upper limit to $|E|$.

Secondly if we are comparing $O((\log|V|^2||E|))$ against something like $O(|V|^2+|E|)$, former will be always better than the latter , since $O(\log(|V|^2)|E|) = O(\log|E|+2\log|V|)$.

So the question is, whether to analyze algorithms in terms of $|E|$ (i.e $|E|$ and $|V|$) or only in terms of $|V|$.

Of course what you say about needing to relate $|V|$ and $|E|$ is correct. However, whenever a complexity is stated in terms of $|E|$, it is better than, say, substituting $|V|^2$ for $|E|$. Note that $|E|$ is always $O(|V|^2)$ even for the cases when it is smaller, for example, for trees. $O()$ is upper bound.

If the analysis of an algorithm is in terms of $|E|$ than we get the complexity bound for all the cases, whether the graph is dense or sparse. Thus $|E||V|$-time algorithm is considered better than a $|V|^3$-time algorithm.

In the cases, if the graph is a tree, or a graph with a max degree $d=O(1)$, then $|E|$ is only $O(|V|)$. So, as an example, an $O(|E||V|)$ algorithm will be considered better than $O(|V|^3)$ algorithm. Thus, if we are able to do a tighter analysis, we are sure that the algorithm will fare better in case of non-worst case input.

As pointed by Raphael, $\Theta(|E|)$ is not same as $O(|V|^2)$. $\Theta$ analysis is better wherever applicable. But usually we don't give $\Theta$ analysis, because if we say some algorithm is $\Theta(f(n))$, and for some easy input the algorithm runs in $o(f(n))$ time, our statement will be wrong.

# Answer
> 1 votes
In general all we can say is that $0 \le |E| \le |V|^2$. Thus, $|E| = O(|V|^2)$.

For connected graphs, $|V|-1 \le |E| \le |V|^2$. For many problems, we can show that only connected graphs are of interest (e.g., if the graph is disconnected, we can decompose it into connected components and then solve the problem separately on each connected component). For these problems, $|E| = O(|V|^2)$ and $|E| = \Omega(|V|)$ (i.e., $|V| = O(|E|)$).

---
Tags: algorithm-analysis, landau-notation
---


# Question
Title: Is a graph of zero nodes/vertices connected?
Suppose there is a graph *G* of zero nodes, there is an even number of nodes. By definition of connectivity, the graph *G* is connected when there is a path between every pair of nodes. But there are no pair of nodes since there are zero nodes.

Does this mean *G* is connected because there is a path for every pair of nodes (in this case zero) or would this mean *G* is not connected because there are no paths?

# Answer
> 3 votes
These issues are discussed in the classical paper Is the null graph a pointless concept? by Harary and Read. The conclusion is that usually when we think of graphs, we don't think of them as having zero nodes. Definitions which are equivalent for non-empty graphs can differ on the null graph. Whenever we use null graphs we have to be very careful and choose our definitions according to usage.

Given a definition of connectedness, you can check whether the null graph satisfies it. For example, taking your definition (there is a path connecting any two vertices), the null graph is connected since this condition is satisfied vacuously.

---
Tags: graphs
---


title: Algorithm for projection of polytope

text:
# Question
Title: Algorithm for projection of polytope
Let a convex bounded polytope be given by an intersection of half planes: $Ax \leq b$. Let $z=Cx$ be a vector (in my case $z$ is 2-dimensional, while $x$ has a higher dimension). How can I compute $D$ and $e$ such that $Dz \leq e$ is a projection of $Ax \leq b$ into the $z$-space.

# Answer
Theorem 3 in this paper gives you the algorithm for your case (projection onto a plane). For general dimension the problem is NP-hard.
> 1 votes

---
Tags: computational-geometry, linear-algebra
---


# Question
Title: example for weakly fair v.s. strongly fair scheduling in concurrency
I am having difficult time understanding the difference between weakly fair and strongly fair schedulers. Can someone provide an example and explain how they are different?

for reference, here are the definitions I have of each:

weakly fair: A condition becomes true and remains true at least until after the conditional atomic action has been executed.

strongly fair: If the condition is infinitely often true, a process will eventually see it as true and be able to proceed.

So I think I understand weakly fair, a conditional atomic action will execute when its condition is true, and the condition will remain true until the atomic action has ended.

But I don't see how strongly fair is different from this. for a conditional atomic action, once its condition is true it executes, and because it is atomic, the condition should remain true until it ends, right? this is the same as weakly fair isn't it?

# Answer
> 6 votes
If you are familiar with temporal logic, the difference is quite easy to demonstrate:

Weak fairness is $FGp\to Fq$. That is, if $p$ holds from some point and on, then $q$ will hold eventually.

Strong fairness is $GFp\to Fq$ (or sometimes $GFp\to GFq$). That is, if $p$ holds infinitely often, then eventually $q$ will hold (or $q$ will hold infinitely often, in the second version).

Your description is slightly different from the above, in that your weak fairness has the "until" flavour, but it's the same idea.

To demonstrate the difference in the approaches, think of yourself as a process trying to gain access to some critical section. If you know that the system is weakly fair, then you need to raise a flag saying that you want access, and you have to keep this flag up *all the time*, until you get access. If the system has strong fairness, it is enough that you raise the flag every now and then, and you know that eventually you'll get access.

As an alternative example, children who want attention often go "mom" repeatedly until they are granted attention. This is similar to weak-fairness (of the mother), and as you can see, it prevents the child from doing anything else until granted attention. With a strongly-fair mother, it suffices for the child to say "mom" every few minutes, and go about doing other things in the mean time.

By the way, this question has an excellent answer by Cynthia Disenfeld at quora.

---
Tags: concurrency, process-scheduling
---


# Question
Title: Relationship between formal system and formal languages
In a course of computer science it is common to study the hierarchy of formal languages, grammars, automata and Turing machines. I wonder what is the relationship of these objects with formal systems.

For example, lambda calculus is said to be a formal system. Would its grammar also be considered a formal system?

# Answer
In my opinion, a formal system should have

1. A well defined set of **symbols**.
2. A well defined **grammar**, which tells how well-formed formulas are constructed out of the symbols.
3. One or more well defined **inference calculi**, which might work similar to the inference calculus associated with a grammar.
4. One or more **semantics**, allowing to assign meaning to the formulas, propositions and statements of the formal system.

Even so the last point might be contested, it is the one which is responsible for the significant difference between a formal system, and a grammar or a formal language. The inference calculus of a formal system might indeed coincide with the calculus of some grammar, even so it won't normally coincide with the calculus of the grammar of the formal system itself.

(Even a grammar can have multiple inference calculi, but using multiple inference calculi for one formal system is more common in logic, where you want to prove things like *cut elimination*, or use one formal system as basis for a hierarchy of formal systems.)

A formal language is associated to both a grammar and a formal system. For a formal system, both the set of well-formed formulas, and the set of valid well-formed formulas are formal languages. The formal language is a sort of equivalence resulting from ignoring additional structure like the semantics of the inference calculus, or the finer parts of a grammar. It is one obvious link between formal systems and grammars, but formal systems and grammars can be closer related than expressible by a formal language alone (i.e. they can have an equivalent inference calculus).
> 5 votes

# Answer
Generally speaking, a formal system is comprised of

* a **language** distinguishing its well-formed formulas from those strings over that are not well-formed
* some kind of **semantics** that says which formulas are true and which are not
* **axioms and inference rules** which attempt to generate, computationally, exactly those formulas which are true given the semantics.

We can specify the language of well-formed formulas using a grammar, but a grammar is not itself a formal system.
> 5 votes

# Answer
A *formal language* $\mathcal{L}$ is composed of:

* an **alphabet** of symbols, that is a set of symbols with the particularity that each of those symbols can be specified without reference to any interpretation. The alphabet of a formal language $\mathcal{L}$ is often referred as $\Sigma$.
* a **grammar** that determines which sequences of symbols in $\Sigma$ are **well-defined-formulas** (often called **wffs**) in $\mathcal{L}$.

A *formal system* $\mathcal{S}$ is:

* A formal language $\mathcal{L}$
* A deductive apparatus.

What is a deductive apparatus you may ask?

* An arbitrary set of **wffs** in $\mathcal{L}$ that are **axioms**
* A set of **inference rules** that determines which **wffs** have a relation of "immediate consequence" between them.

Here are a some excellent references whether you want to get started or dive into more meaty stuff:

* *Metalogic: An Introduction to the metatheory of Standard First Order Logic* by Geoffrey Hunter.
* *Automata, Formal Languages and Algebraic Systems* by Masami Ito
> 2 votes

# Answer
What you see in an introductory course in formal languages is just a small sample of the multitude of models used to define and study languages (or functions, numbers, etc.) formally, i.e., regarding their syntactical structure - that has a dynamic component, which we call "computation" -, setting aside what could be considered their *content*, to be "reattached" to these structures *a posteriori*, or not at all. These different models come from different contexts and have different applications, theoretical as well as practical.

The language used to describe these models can also be formalized, so you have grammars both as formal systems and as languages. This kind of circularity is problematic, but unavoidable, and in many cases desirable.

The notion of formal system as it is used in computer science has to do historically with the investigation of formal properties of mathematical logic systems. The standard definitions you will see in other answers come from this common origin. There are other kinds of formal systems in other fields of research, the term is polysemic. The distinction between concepts of form and content depends on where you're coming from.
> 1 votes

# Answer
I'm looking for the same question, and seems there are no clarity. I hope someone could give us.

See, for instance, what Levelt state in his book ("*An Introduction to the Theory of Formal Languages and Automata*" Cap1, p. 1):

> From a mathematical point of view, **grammars are FORMAL SYSTEMS**, like Turing machines, computer programs, prepositional logic, theories of inference, neural nets, and so forth. \[\]

Despite of this, it's a really matter whats others answers pointed out here, because formal grammars seems truly miss some fundamental attributes (i.e. deductive apparatus) to be marked as formal systems.

However, if a Turing machine is a formal system \[\], and formal languages (and its representations, grammars) are equivalents to them: why grammars is not a formal system too?

I hope this consideration, event though are not conclusive may animate some improved answer to this problem.
> 0 votes

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


# Question
Title: Difference between system calls, system call interface and API?
Lets take POSIX, whats the difference between POSIX API, libc and actual system calls?

# Answer
> 2 votes
I'll start with system call.

> *a system call is how **a program requests a service from** an operating system's **kernel**. This may include hardware-related services (for example, accessing a hard disk drive), creation and execution of new processes, and communication with integral kernel services such as process scheduling. System calls provide an essential interface between a process and the operating system.* Wiki

Another definition.

> *A system call, sometimes referred to as a kernel call, is a request by an active process made via a software interrupt for a service performed by the kernel.* (Source)

## The library as an intermediary

> *Generally, systems provide a **library or API that sits between normal programs and the operating system**. On Unix-like systems, that API is usually part of an implementation of the C library (libc), such as glibc, that provides wrapper functions for the system calls, often named the same as the system calls they invoke.....For **example**, in Unix-like systems, `fork` and `execve` are C library functions that in turn execute instructions that invoke the `fork` and `exec` system calls. Making the system call directly in the application code is more complicated and may require embedded assembly code to be used (in C and C++) as well as knowledge of the low-level binary interface for the system call operation, which may be subject to change over time and thus not be part of the application binary interface; the library functions are meant to abstract this away.* Wiki

You may find a couple of popular POSIX system calls here.

## TL;DR

So, to summarize, a system call is a request to the kernel for a service. The **system call interface** is the basic interface between a program and the kernel. The programming library, e.g. libc, has APIs on top of the basic system calls, provided by the kernel, which further ease the job of the developer.

---
Tags: terminology, operating-systems
---


title: What is a stateful computation?

text:
# Question
Title: What is a stateful computation?
I am reading about a specific field of probabilistic programming, and trying to understand what the term "stateful computation" means.

See: http://projects.csail.mit.edu/church/wiki/Simple\_Generative\_Models

(search for "XRP")

# Answer
> 5 votes
Stateful computation basically means that the model of computation has got a memory storage to store information, and it uses this information to compute. For example, let us say you have a function $f()$ computing something using state information. Then, if you do,

$x\_1 = f()$
$x\_2 = f()$
$x\_3 = f()$
...

$x\_1, x\_2, x\_3,.. $ may be all different. In functions, defined as mapping in set theory, we cannot have functions returning different values from different calls. We will need to define something like $\langle y, store\_{i+1}\rangle = f(\langle x, store\_i\rangle)$ in that case. A sample code for $f()$ that is stateful is given below.

```
function f()
output: integer x;

global integer store initialized to 0;

x = store
increment store by 1
return x

```

This function will return 1, 2, 3, 4, ..., in sequence when it is called multiple times. Here store is the memory storage it uses to compute differently.

The function can also use other inputs to compute its output, such as events from an event queue, input data, interactive data, etc. but stateful computation must assume an underlying saving of state in the model of computation.

By the way, the model of computation for computers is Turing Machine, which can be thought as stateful computation if you use functions as subroutines, i.e., you do not start Turing machine from beginning at every function call.

---
Tags: terminology, programming-languages, randomized-algorithms
---


# Question
Title: CLRS: Asked to prove a result and then told to give a counter example
I am reading Introduction to Algorithms, and I am stuck at this execercise in the Appendix:

> * Argue for any integers $n \ge 0$, $j \ge 0$, $k \ge 0$ and $j + k \le n$.
>
> $${n \choose j + k} \le {n \choose j} {n-j \choose k}$$
>
> Privde both an algebraic proof and an argument based on a method for choosing $j+ k$ items out of $n$. Give an example in which equality does not hold.

Here I am asked to prove it and then give a counter example. I can't seem to find any problem with the proof or the couter example, $n=4$, $j=k=1$. Puzzeled!

Here is a proof:

> First, let's establish that, $j!k!\le (j+k)!$. Both sides have the same number of terms, but the right side has $k$ terms more - $(j+1)(j+2)\ldots(j+k)$ - that are greeter than the corresponding terms on the left side $1\cdot2\cdot\ldots\cdot k$.
>
> Thus:
>
> $${n \choose j}{n-j \choose k}=\frac{n!}{j!(n-j)!}\frac{(n-j)!}{k!(n-j-k)!}=\frac{n!}{j!k!(n-j-k)!}\ge\frac{n!}{(j+k)!(n-j-k)!}={n \choose j+k}$$

# Answer
> 1 votes
You aren't asked to give a counterexample to the proof, as that would be impossible.

Instead, they're asking for an example where *equality* does not hold, that is, the left hand side is strictly smaller than the right hand side. That's not a counterexample since the theorem states *less or equal*.

---
Tags: combinatorics, discrete-mathematics
---


# Question
Title: Every non deterministic Turing machine has an equivalent deterministic Turing machine Formal proof
is there exist a formal proof for Equivalence of deterministic and non deterministic Turing Machine ? i read Martin Davis and Sipser's book and there is no formal proof

# Answer
> 3 votes
There is a full proof in Hopcroft, Motwani and Ullman's Book (John E. Hopcroft and Rajeev Motwani and Jeffrey D. Ullman (2003). Introduction to Automata Theory, Languages, and Computation). There is an outline of proof in the wiki: Equivalence of DTM with NDTM.

---
Tags: turing-machines, simulation
---


# Question
Title: Proving following regular expressions equal to one another?
How would I go about proving the following two regular expressions are equal to one another:

```
( a + b )* a ( a + b )* b( a + b )* = (a + b)* ab(a + b)*

```

I can "see" why they are equal to one another because the second `( a + b )*` is a redundant term as the expression will always have an ab together. But how can I formalize this and show, in general, that this is true ?

# Answer
Convert both regular expressions to a DFA, compute the symmetric difference of the two DFA's using a product construction, and then check whether the result accept the non-empty language. Each of those steps is described here on this site. See also Does this regular expression equal this automata? for a very similar question.
> 4 votes

---
Tags: regular-languages, finite-automata, proof-techniques, regular-expressions
---


# Question
Title: How do you find an infinite regular language that is a subset of a non-regular language?
In order to do this, we would probably need the non-regular language to be infinite as well, then find some definition for the non-regular language in order to fulfill the requirement, but I don't know how to construct one.

# Answer
Note that any non-regular language is infinite, since any finite language is regular.

Instead of searching for infinite regular subset in some given non-regular language, why don't we try to construct a non-regular language that contains an infinite regular language?

To do that we can take some context-free language, which is not regular, e.g. classical $a^nb^n, n \ge 0$, and "add" some infinite regular language to it. By "add" I mean the union operation on sets.

I should notice that one has to be careful while "adding" an infinite regular language to a non-regular one, since $L(a^nb^n) \cup \Sigma^\* = \Sigma^\*$, which is obviously regular.

So let's take a regular language $L(a^\*)$, which has only one string in common (the empty string) with $L(a^nb^n), n \ge 0$ as our candidate "addition".

It's easy to prove the language $L(a^\*) \cup L(a^nb^n), n \ge 0$ is non-regular (context-free). And its regular subset $L(a^\*)$ is infinite.
> 2 votes

# Answer
A general aproach consist in making a non-regular language by the union of a regular language with a language that is known to be non-regular and then prove that the resulting language is irregular by using the closure property of intersection between regular languages. For example as Anton said if you construct $L= \mathscr{L}(a^\*)\cup \\{a^nb^n : n\geq0\\}$ then $L$ is irregular(can be proved using the closure property) and $\mathscr{L}(a^\*)$ is regular as requested.

But you have to be carefull. You can choose two languages with a regular union. For example:

$L= \mathscr{L}(a^\*b^\*)\cup \\{a^nb^n : n\geq0\\}=\mathscr{L}(a^\*b^\*)$ is regular.

Here $\mathscr{L}(a^\*b^\*)$ overrides the non-regular language. This can be easily corrected by choosing a better non-regular language:

$L= \mathscr{L}(a^\*b^\*)\cup \\{a^nb^nc^n : n\geq0\\}$ is non-regular.
> 2 votes

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


title: proof using induction of automaton

text:
# Question
Title: proof using induction of automaton
How I can explain this. Consider the following automaton, $A$.

1. Prove using the method of induction that every word/string $w\in L(A)$ contains an odd number(length) of $1$'s.
2. Show that there are words/strings with odd number(length) of $1$'s that does not belong to the language $L(A)$. Describe the language $L(A)$.

Here is what I did. For 1st question

q1 is the up-left circle , q2 the up-right, q3 down-left, q4 down-right.

and the transition table

```
     0  |  1
--------------
q1  q3    q4
q2  q2    q1
q3  q3    q4
q4  q2    q1

```

basic inductive step: I verify that is valid for word = 1 (odd number of 1's) From state q1 we go to q4 (final accept state)

induction hypothesis: I assume that is valid for n = 2 * k +1 (n odd number 1's)

inductive step: 2(k+1) +1 I prove that is valid for 2(k+1) +1=\> 2(k+1) +3=\> 2(k+1)

For second Suppose the word =1000 or 10 with odd length of 1's , the final state is not the acceptance one.

Can anyone tell me if this I wrote is correct?

# Answer
> 0 votes
In this case you might be able to state an invariant statement of the form: "For a word of the form $w1$ the unique path on $w1$ ends in state $q\_0$ if $w$ contains an even number of $1$'s and in state $q\_1$ otherwise".

The basis of the induction considers words $w$ with zero $1$'s, so look where $0^\*1$ ends in. Then an inductive step, using the inductive hypothesis.

Start by assigning names to the states.

# Answer
> 0 votes
You have three questions here; we are more comfortable with one question per post. Having said that, here are some hints.

For the first part, could you do the proof on the simpler language over $\\{1\\}$? In other words, ignore any 0's and see what you can do.

For the second part, what must a string in $L(A)$ end with?

Finally, welcome to the site!

---
Tags: automata, finite-automata, proof-techniques, induction
---


# Question
Title: Where can I find information on Data Structures used in common software?
As part of a course I am teaching on Data Structures, I want students to research and present the use of Data Structures in popular software/services. However, basic googling shows me that this information is not so readily available.

Can someone point me to the right resources that I may share with the students as a starting point for their research?

EDIT

Judging from the received replies, the original question is not sufficiently clear so I am adding more details.

I am looking for resources of the type that state, for example, that *service-x* uses *data-structure-a* in order to perform *functionality-y* because of *property-b*. This is the ideal case. Other resources that provide similar information are also welcome.

# Answer
Off the top of my head:

Every modern operating system uses balanced binary search trees to implement the virtual memory map of a process. Windows uses splay trees, Linux and OS X use red-black trees, and Solaris uses AVL trees. They do this because the operating system needs to store the virtual memory map in order (by virtual address), to allow for fast insertion and removal, and to look for unused regions where it could allocate space.

Many modern 3D games (e.g. anything which uses a recent version of Unreal Engine) use octrees to determine what objects are visible to the camera. They do this because it's quite efficient to calculate what nodes overlap with a camera's view frustum.

Many (if not most) routers use radix trees to implement routing tables. They do this because it is often the prefix of a network address (i.e. the most significant bits) which is important, not the whole key. Moreover, lookup takes time which only depends on the size of the address, not the number of routing table entries, which makes predicting timing easier.

Hash tables are, of course, used everywhere. Antivirus software uses it to perform lookups in its database of known malware, word processors use it to perform spelling checks, etc.

Graph data structures are used by spreadsheets to implement evaluation. Think of each occupied cell as a node, and draw an arc between to cells if the value of one directly depends on the value of the other. When an entry changes in a cell, the graph is traversed to determine which cells need updating based on that change.
> 10 votes

---
Tags: data-structures, reference-request, applied-theory
---


# Question
Title: CFG for words that are not a concatenation of the same word
I am teaching myself formal languages, and yesterday i got stuck at an exercise asking for a context free grammar for the language:

$ L = \\{x \in \Sigma ^{+} | \ \forall w \in \Sigma ^{+} \ x \neq ww\\} $ with $ \Sigma = \\{a,b\\}$

I am trying some rules of the form

$L \Rightarrow a | b $

$S \Rightarrow aSbS\ |\ bSaS\ |\ L\ |\ ab\ |\ ba $

However this is wrong since for example the grammar does not accept 3-symbol strings. I am a little bit stuck with it so any help would be greatly appreciated.

# Answer
> 1 votes
The question has been asked before, but since it's faster to describe the answer than to find the previous question, I'll outline the answer here.

We can characterize words in $L$ as belonging to one of two classes:

1. Words of odd length.
2. Words $z\_1 \ldots z\_n w\_1 \ldots w\_n$ where $z\_i \neq w\_i$ for some $i$.

It is easy to generate words of the first type. As for words of the second type, for fixed $i$ and $n$ we can generate them using rules of the form $\Sigma^{i-1} a \Sigma^{n-i} \Sigma^{i-1} b \Sigma^{n-i} = \Sigma^{i-1} a \Sigma^{i-1} \Sigma^{n-i} b \Sigma^{n-i}$ and its counterpart with $a,b$ replaced by $b,a$. I'll let you figure out how to generate all of these words (for *all* $i,n$).

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


# Question
Title: How to treat $\epsilon$ and '$' in top-down predictive parsing (predict table)?
How to treat $\epsilon$ and '\\$' in top-down parser using predict table?

The construction of the predict table

> Given a product $X \rightarrow w$, row $X$ and column $t$
> -Mark $X \rightarrow w$ for each $t \in FIRST(w)$
> -If $NULLABLE(w)$, then mark $X \rightarrow w$ for each $t \in FOLLOW(w)$ as well

says to create columns for all terminal symbols. $\epsilon$ is a terminal symbol so it's naturally added as a column.

However, I've somehow interpreted that I could/should add '\\$' as a terminal symbol as well. Basically because '\\$' is used in the FOLLOW sets (and the FOLLOW sets don't contain $\epsilon$).

But does this create redundancy since then the table would hold basically the same predict rules for '\\$' and $\epsilon$ (at least in the implementation I have here)?

The rules given here also treat '\\$' and $\epsilon$ as if they were separate:
http://www.jambe.co.nz/UNI/FirstAndFollowSets.html

The FOLLOW sets basically use '\\$' in place of $\epsilon$, but the predict table uses $\epsilon$, because it's a terminal symbol.

# Answer
> 3 votes
> $\epsilon$ is a terminal symbol

No. $\epsilon$ is the empty string, i.e. no symbols at all.

> However, I've somehow interpreted that I could/should add '$' as a terminal symbol as well.

Yes, `$` is the special symbol that marks the end of input, and you may have to do things at that place and when you want to go past it, you are done (or in situation of error for LR parsing if the stack is not empty).

> The rules given here also treat '$' and ϵ as if they were separate: http://www.jambe.co.nz/UNI/FirstAndFollowSets.html

Considering $\epsilon$ as a symbol to be put in $FIRST$ could be an worthwhile implementation trick instead of computing $NULLABLE$ separately (I haven't tried it, at first sight it seems to break useful properties and to add as much complexity as it removes, see the point 4 in the computation of $FIRST$), but it is nothing more than an implementation trick.

---
Tags: recursion, parsers, ll-k
---


# Question
Title: Train a neural network to play tic tac toe using a genetic algorithm
I have an assignment for school, in which I have to build a neural network that will play tic tac toe, using genetic algorithms for training. The thing is that I am clueless on how to connect the two. I need help in the design. Should use the GA to generate game boards, to serve as input for the neural network. Or, should I generate the NN weights with the GA. In both cases. I'm having a really hard time with this subject, but I find it extremely fascinating. Any help would be much appreciated. Thanks

# Answer
this is an unusual assignment or exercise for several reasons. tic tac toe is not a complicated game, there is not a large "state space" so an optimal algorithm is possible even by eg a "relatively small" finite state machine. so even a genetic algorithm or neural network *alone* would be sufficient (in fact, capable of playing a perfect game) and also, from a practitioner pov, overkill. it suffices as a "toy problem" but almost even too simple to fully demonstrate these techniques. breaking down the problem into a machine learning approach aka "decomposition" is part of the art/ science of the field. here are a few relatively basic/ straightforward possibilities.

1. genetic algorithm alone: let the candidate solutions aka chromosomes be represented as strings with alternating moves. the fitness function evaluates who wins and if the strings represent valid moves between the two players. it will not take long to find/ enumerate all possible game sequences.
2. neural network alone: input is (an encoding of) the opponents move, output is the computers move. a data generator must pick valid moves by the opponent.
3. combination (even bigger overkill): a common scenario in NN+GA technology is for the GA to be used to generate NN architectures. the GA string determines the NN architecture. eg size and possibly connectivity of the different layers. the fitness function is the results of training/ evaluating the NN on the particular GA architecture (ie chance of the computer winning).

and of course there are many other ways to combine NNs+GAs and other ways to decompose the problem into NNs or GAs alone.
> 1 votes

---
Tags: neural-networks, genetic-algorithms
---


# Question
Title: A string that takes a DFA from any state to a given state?
EDIT: as templatetypedef commented, this problem is to find out if a DFA has a synchronizing word (a.k.a. "reset sequence").

Given a finite state set $Q$, a finite alphabet $\Sigma$, and a transition function $\delta : Q \times \Sigma \rightarrow Q$, I want to find out if there is a state $q\_f \in Q$ and a string $s \in \Sigma^\*$ such that for every state $q\_0 \in Q$ (including $q\_f$), the DFA $\left( Q, \Sigma, \delta, q\_0, \left\\{ q\_f \right\\} \right)$ accepts $s$. ($q\_0$ is the initial state; $q\_f$ is the only accepting state.)

In other words, if you think of a string as a list of directions for navigating the DFA, I want to find out if there is a list of directions that takes you to the same state no matter where you started. (Knowing the existence is enough; I do not need to know the state or the string itself.)

I have tried this algorithm:

1. Reverse the transitions in $\delta$ to form an NFA.
2. Convert the NFA into a DFA where each state corresponds to a subset of the NFA's states.
3. For each state $q \in Q$, search the new DFA for a path from $\left\\{ q \right\\}$ to $Q$. (I just do a depth first search.)
4. Iff one of these searches is successful, then the answer to the question is "yes".

This algorithm is correct, but it runs in exponential time and space, and it takes too long to complete. (My input DFAs have tens of states.) Note that I do not actually construct a DFA from the NFA -- instead, I perform the search on the NFA and I remember which subsets of its states I have visited.

Is there a way to improve my algorithm? Are there other algorithms to solve this problem? (Or at least, algorithms that would be useful?) Are there any properties of automata and regular languages that I can take advantage of?

# Answer
> 3 votes
It turns out that there exists a string that takes all states to the same state iff for each *pair* of states, there exists a string that takes both states to the same state.

Using this fact, I had success with the following algorithm:

* Generate a new DFA from the Cartesian product of the old DFA with itself. (The new DFA contains $\left(a,b\right) \overset{x}{\rightarrow} \left(c,d\right)$ iff the old DFA contains $a \overset{x}{\rightarrow} c$ and $b \overset{x}{\rightarrow} d$, where $x$ is an input symbol and $a$, $b$, $c$, and $d$ are states.)
* For each state $\left(a,b\right), a \neq b$ in the new DFA, search for a path from $\left(a,b\right)$ to a state of the form $\left(c,c\right)$. (If found, then that means there is a string that takes the old DFA from $a$ to $c$ and from $b$ to $c$.)
* There is a reset sequence for the old DFA iff every search in the above step yields such a path.

More info:

https://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-90.pdf

---
Tags: algorithms, automata, finite-automata, search-algorithms
---


# Question
Title: Analysis of the following integer program
So the knapsack problem has an integer programming formulation as follows,

$$ \max\_x v\cdot x\\s.t \\x\_i \in \\{0,1\\}\\w\cdot x \leq C$$

Now consider the second integer program which might be a variation of the knapsack integer program.

$$ \max\_x v\cdot x\\s.t \\x\_i \in \\{0,L\_i\\}\\ x\_i \leq R \cdot \delta\_i\\ \delta\_i \in \\{0,1\\}\\ \sum\_i \delta\_i = k$$ where $v\_i$ is item's $i$ value, $L\_i$ and $k$ are constants, and $R = \max{\\{L\_1,L\_2,...L\_d\\}}$.

* Is there a dynamic programming solution or an approximation algorithm for the second integer programming problem ?
* Is it possible to use the solution of the knapsack problem to warm
start or partially solve the second integer programming ?

Thanks!

# Answer
A simple greedy approach works here: choose the $k$ elements having maximal $v\_i L\_i$.
> 2 votes

# Answer
Yes, the problem can be solved with dynamic programming, in pseudo polynomial time. Let $f(j,k)$ be the largest value attainable for a particular value of $k$ when we constrain to use only the first $j$ elements of $x$ (i.e., when we are constrained to $x\_{j+1} = x\_{j+2} = \dots = x\_d = 0$). Then you can express $f(j,k)$ in terms of values of the form $f(j',k')$ where $(j',k') \le (j,k)$. The running time will be $O(dk)$.
> 1 votes

---
Tags: algorithms, knapsack-problems, integer-programming
---


# Question
Title: How is the space hierarchy theorem different for non space constructible functions?
Sipser first introduces space constructible functions. Then uses the definition to prove the space hierarchy theorem:

> if f(n) is a space constructible function then there are languages that can be decided in O(f(n)) space but not in o(f(n)) space.

The author only mentions as most encountered functions are space constructible, it is a good assumption. Are there any cases where non space constructible functions of are interest ? How does the space hierarchy theorem changes under such conditions ?

# Answer
> 4 votes
Your question is answered on Wikipedia: for any $s(n)$, and $f(n) = O(s(n))$, and any *computable* $g(n) = o(s(n))$, $\mathsf{DSPACE}(f(n)) \neq \mathsf{DSPACE}(g(n))$. This is a result due to Geffert.

---
Tags: complexity-theory, space-complexity, lower-bounds
---


# Question
Title: Finding Connected Components Dependent on Order?
It seems to me that the outcome of a connected components algo is dependent on the start vertex. Is this correct?

Say we had the graph

If we started our connected component search from the vertex on the upper right then we would end up with different set of connected components than if we started our search with the vertex in the upper left?

Is this correct?

# Answer
There's a few things we need to clear up.

First, the graph you show is directed. Are we talking strongly-connected, weakly connected, bilaterally-connected, etc. What you mean by connected here matters.

Secondly, in such an algorithm, usually you keep searching until each vertex in the graph has been assigned a component.

So, if you use the algorithm(s) properly, and keep searching until all vertices have been classified, the output will not depend on what vertex you start at. Each vertex belongs to exactly one connected component (whichever variety you choose), and a correct algorithm will assign it as such, regardless of the start vertex.

However, if you start at a vertex, you might not find all vertices just in the search starting from that vertex, which is why you need to repeat your search until you have seen all vertices.
> 3 votes

---
Tags: graphs, graph-traversal
---


title: About the Max-Cut SDP

text:
# Question
Title: About the Max-Cut SDP
The Max-Cut optimization problem on a graph $G=(V,E)$ can be written as the question of wanting to maximize the function $\frac{1}{4} \sum\_{(i,j) \in E } (x\_i -x\_j)^2$ under the constraint $x\_i^2 = 1, x\_i \in \mathbb{R}, \forall i \in V$.

Now the usual SDP relaxation is to lift the $x\_i$s to vectors $\vec{x\_i} \in \mathbb{R}^d$ for some $d$ with the new objective function to be maximized being $\frac{1}{4} \sum\_{(i,j) \in E } \vert \vert \vec{x\_i} - \vec{x\_j} \vert\vert \_2 ^2$ under the new constraint being $\vert \vert \vec{x\_i} \vert \vert \_2 ^2 = 1$.

* I wonder why in the usual SDP relaxation we use the $l\_2$ norm. Is that just convenience or is there some optimality argument about it? Like one could have as well for any $4$ integers $p,q,r,s$ thought of,

maximizing $\sum\_{(i,j) \in E } \vert \vert \vec{x\_i} - \vec{x\_j} \vert\vert \_p ^q$ under the constraint being $\vert \vert \vec{x\_i} \vert \vert \_r ^s = 1$.

I believe this optimization problem would still give the max-cut?

Beyond the fact that such an optimization would probably be very hard to do, is there any fundamental reason why we do not do such a formulation of optimizing the $q^{th}$ power of the $p-norm$ under a constraint fixing the $s^{th}$-power of the $r-norm$?

* (will there emerge constraints on the integers $p,q,r,s$ for this to work?)

---

For example,

Even before the relaxation one could have as well written the optimization question as wanting to optimize $\frac{1}{16} \sum\_{(i,j) \in E } (x\_i -x\_j)^4$ under the constraint $x\_i^2 = 1, x\_i \in \mathbb{R}, \forall i \in V$. I believe this would still give the same max-cut!

And then one might have thought of its "natural" SDP relaxation to be,

maximizing $\frac{1}{16} \sum\_{(i,j) \in E } \vert \vert \vec{x\_i} - \vec{x\_j} \vert\vert \_4 ^4$ under the constraint being $\vert \vert \vec{x\_i} \vert \vert \_2 ^2 = 1$.

* Do we know that say the above SDP won't beat the $0.878$ factor?

# Answer
An SDP relaxation is not an arbitrary optimization problem; rather, it consists of optimizing a linear function over semidefinite and linear constraints. One general formulation of SDP is $$ \begin{align\*} &\max \sum\_{ij} c\_{ij} x\_{ij} \\ s.t. \\;\\;& X \succeq 0 \\ & A \mathbf{x} = \mathbf{b} \end{align\*} $$ Here $X$ is the matrix whose entries are $x\_{ij}$, and $\mathbf{x}$ is a vector whose entries are $x\_{ij}$ (in some arbitrary order).

Standard accounts on semidefinite programming should explain why the SDP relaxation that you describe can indeed be formulated in this form. In short, the idea is that $x\_{ij}$ is going to represent the inner product $\langle \vec{x}\_i, \vec{x}\_j \rangle$. The fact that $X$ is positive semidefinite is equivalent to the existence of such vectors $\vec{x}\_i$. The objective function $\sum\_{(i,j) \in E} \\|\vec{x}\_i - \vec{x}\_j\\|^2$ can be written as a linear combination of the $x\_{ij}$, and the constraints $\\|\vec{x}\_i\\| = 1$ can be written as linear constraints on the $x\_{ij}$.

Why do we care about semidefinite programs? Because we know that they can be solved (approximately, but arbitrarily well) in polynomial time. This is not true for an arbitrary optimization problem.

There is some evidence that the Goemans–Williamson constant $0.878$ is best-possible for polynomial time algorithms. Namely, this is the case if Khot's Unique Games Conjecture holds. Under this conjecture, Raghavendra showed that SDP relaxations are optimal for a wide class of problems (constraint satisfaction problems).
> 1 votes

---
Tags: complexity-theory, np-complete, optimization, np-hard, convex-hull
---


# Question
Title: Proving that an algorithm $A$ runs in $\Theta(f(n))$ time in the worst-case
I wanted to understand how to establish both the lower $\Omega$ and upper bound $O$ on an algorithm to conclude it runs in $\Theta$ (note that I am not trying to prove that the algorithm is the most optimal and that no better algorithm exists).

To establish a $O$ I thought that one just has to prove somehow that the algorithm will never take more than $f(n)$ (for sufficiently large inputs) **for alll** possible input to the algorithm $A$. I think that should establish an upper bound in the worst-case, right? (since we are considering an upper bound for all inputs, it satisfies the worst-case scenario because it considers **every single** input).

But to establish a $\Omega$ in worst-case we need to argue that it will take at least $f(n)$ for **some** family of inputs (of size $n$). Is this correct?

My reasoning: In worst-case analysis we care about the performance of our algorithm in the worst-case. So to establish a $\Omega$ we need to show that there is exists some input (i.e. one that makes the specific algorithm perform the slowest) that could be given to use adversarial (that is why we need the quantifier exists rather than for all). So if there is some input that makes $A$ run in $f(n)$ in the worst case, an adversary could give us that input every time so we always run in $f(n)$. So we only need one to exists. But if we show we can never run in more than $f(n)$ then that input is really the "worst-case" because there cannot be any input that makes us run is more than $f(n)$. Is that sort of right? Basically, there exists guarantees worst case lower bound since an adversary could always give us that input and the for all guarantees a upper bound on any other potentially "worst" input.

# Answer
> 0 votes
Your observations are correct for the worst-case time complexity, which is the most common measure of time complexity, other than a small point – usually we prove an upper bound of $Cf(n)$ and a lower bound of $cf(n)$, where the constants $c,C$ need not match (and usually aren't explicit, being instead hidden in asymptotic notation).

There is a subtlety here – as you correctly mention, formally speaking we need a hard instance for *every* $n$. Usually this is not a problem since instances can be "padded" – if we have a construction that only works directly for even $n$, perhaps we can pad it to get a construction that also works for odd $n$. But in computational complexity we are sometimes considering more general and abstract cases in which this is not the case, and the only guarantee is that the running time is $f(n)$ for *infinitely many $n$*. We denote this by $\Omega^\infty(f(n))$ or $\Omega\_\infty(f(n))$. This is the negation of $o(f(n))$, that is, all we can conclude if $o(f(n))$ *doesn't* hold.

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


# Question
Title: Longest path in a graph with special property
I have a special graph in which I have two types of edges only, say one with **type 0** and one with **type 1**. Now I have to find a longest path in the graph such that it starts with a vertex then follows as many type 0 edges as it can and then again start with a vertex and follows as many type 1 edges it can. The length of the longest path will be number of distinct vertices in both the paths. (If some vertex coincide count it once.)

**Note** : The graph is **undirected**, heavily contains **cycles** and has upto **10^6 vertices**. So I would need a O(n) algorithm.

P.S : Sorry forgot to give the more important information, for every vertex there are 0 or 2 edges of each type always.

# Answer
As Raphael pointed out, this problem is also NP-complete. There is an easy reduction from longest path problem to this problem. Just take the graph of longest path problem and label all of the edges type-0. There won't be any type-1 edge. This labeled graph will have a longest path of length $k$ iff original graph has a longest path of length $k$.

This proves the NP-hardness of the problem.

It is easy to see that the problem is in NP, the NDTM machine for the problem will be similar to the longest path problem. Both this add to make the problem NP-complete.

But if you are happy with any kind of approximation, then you can refer Approximation to longest path and modify the algorithm to suit your purpose. However be prepared that the modification may not be trivial.
> 1 votes

---
Tags: graphs, graph-traversal
---


# Question
Title: Ford-Fulkerson Algorithm not "pushing back" flow
I am told that with every flow network, the Ford-Fulkerson algorithm produces an execution that never decreases the value of the flow on any of the edges (i.e. never “pushes back” the flow on any of the edges). I am wondering how that can be possible. Can we choose augmenting paths that allow us to never "push back"?

# Answer
> 3 votes
No, it is not true that *"the Ford-Fulkerson algorithm produces an execution that never decreases the value of the flow on any of the edges"*. If you look at the wiki article of Ford and Fulkerson method you will see the following pseudocode:

Algorithm Ford–Fulkerson
Inputs: Given a Network $G = (V,E)$ with flow capacity $c$, a source node $s$, and a sink node $t$
Output: Compute a flow $f$ from $s$ to $t$ of maximum value

$f(u,v) \leftarrow 0$ for all edges $(u,v)$
While there is a path $p$ from $s$ to $t$ in $G\_f$, such that $c\_f(u,v) \> 0$
for all edges $(u,v) \in p$:
Find $c\_f(p) = \min\\{c\_f(u,v) : (u,v) \in p\\}$
for each edge $(u,v) \in p$
$f(u,v) \leftarrow f(u,v) + c\_f(p)$ (Send flow along the path)
$f(v,u) \leftarrow f(v,u) - c\_f(p)$ (The flow might be "returned" later)

In the last line $f(v,u)$ is clearly decremented.

In the example below one will have to decrease flow in the middle edge to get max-flow. There is no other way.

If you want to know, if there exist a sequence of augmenting paths that never decrease the flows, then the answer is possibly yes. Proof might be non-trivial though.

---
Tags: algorithms, network-flow, ford-fulkerson
---


title: Finding a way out of a polygon

text:
# Question
Title: Finding a way out of a polygon
There is a simply-connected polygon $C$. It contains $n$ pairwise-interior-disjoint simply-connected polygons, $D\_1,\dots,D\_n$:

The goal is to select one of the polygons, say $D\_i$, and attach to it a polygon $E\_i$ such that:

* $D\_i\cup E\_i$ is still simply-connected.
* $E\_i$ is interior-disjoint from all other polygons $D\_i$.
* $D\_i\cup E\_i$ is connected with the exterior of $C$:

Is there an algorithm, preferably published, that solves this problem in time polynomial in the representation of the problem (e.g. total number of vertices of all polygons)?

# Answer
> 6 votes
Basically this is shortest path problem in polygon with holes. There is no constraint in taking $E\_i$ as a path of negligible width.

If you just want to connect internal holes to outside boundary without caring about the path length, then just take any point on the boundary of interior hole and calculate a path to any point on the outer boundary. I don't know your application, but probably you are looking for minimum link rather than minimum euclidean distance, in that case minimum link path would be better.

References:
1) S. K. Ghosh and D. M. Mount. An output-sensitive algorithm for computing visibility graphs. SIAM Journal on Computing archive Volume 20 Issue 5, Oct. 1991 Pages 888-910 (for shortest paths among obstacles)
2) J. Hershberger and S. Suri. Efficient computation of Euclidean shortest paths in the plane. In Proc. 34th Annu. IEEE Sympos. 1993.
3) Joseph S. B. Mitchell, Günter Rote, and Gerhard Woeginger: Minimum-link paths among obstacles in the plane. Algorithmica 8 (1992), 431-459.

However, I should warn you, all the implementations for shortest path, or shortest link path use triangulation for which the optimal algorithm is not very practical. You can however use any sub-optimal algorithm which may be more efficient for your purpose.

The above algorithms are all polynomial in input size.

---
Tags: reference-request, computational-geometry
---


title: Calculating disk seek times

text:
# Question
Title: Calculating disk seek times
I have a system where disk requests come to a disk drive for cylinders in the order 10, 22, 20, 2, 40, and 38 at a time when the disk drive is reading from cylinder 20. The seek time is 6ms per cylinder. I have to find total seek time if the disk scheduling algorithm is First-Come-First-Serve (FCFS).

To find the answer I used a formula:

total seek time=0.254\*sqrt(d)(for each cylinder and sum them)

But that gave the incorrect result. What formula(s) should I be using to handle questions like this?

# Answer
@tonny, I am also found this example from a book, I think the number 6 is missed after the number 40 in the example. The correct order is 10, 22, 20, 2, 40, 6 and 38. So if it starts from cylinder 20, You can write it as, -\> (20), 10, 22, 2, 40, 6, 38 -\> (20-10)+(10-22)+(22-2)+(2-40)+(40-6)+(6-38) -\> 10+12+20+38+34+32 -\> 146. So seek time is = 146\*6 876 ms.
> 1 votes

# Answer
You state that *the seek time is 6ms per cylinder*. That means: take the distance (in *cylinders*) that you move and multiply it by 6ms.

You are starting on cylinder 20, then moving to cylinder 10: that is 20-10=10 cylinders difference, so 6ms\*10 = 60ms. Then you move from cylinder 10 to cylinder 22: that is 22-10=12 cylinders difference, so another 6ms\*12 = 72ms. And so on.
> 0 votes

---
Tags: operating-systems, memory-hardware
---


# Question
Title: Which in-memory data structure can accommodate billions of md5 value?
For my application, I have to store billions of md5 values, and before storing new md5 I wanna make sure that it doesn't exist already in it. I tried using hash data structure, it worked well but no of lookups goes high with table entries. I tried using trie, each node storing a byte, but the memory consumption is too high. As each node required 256 pointer for successor on next level. Can anyone suggest better data structure which could use less space as well as no of lookups is The ?

# Answer
> 1 votes
Maybe you can use a binary trie (critbit tree?) that splits in two on each node instead of 256? Of course you get many more nodes, but they are a LOT smaller. An example implementation in Java is here: critbit

---
Tags: data-structures, dictionaries
---


title: Structural induction on generic list

text:
# Question
Title: Structural induction on generic list
In preparation for an exam, I've come upon the following problem. Given the constructors :

```
[]: -> T LIST

[a]:T-> T LIST

cons(a,x) : T x T LIST -> T LIST ( a is added to the beginning of the list)

```

And the functions :

```
size(l) : T LIST -> N (number of elements in l)

reverse(l): T LIST -> T LIST ( reverses the order ofthe elements in the list)

unique(l) : T LIST -> T LIST - returns a list of the elements in 'l' that only appear once

repeated(l) : T LIST -> T LIST - returns a list of the elements in 'l' that appear more than once

max?(e,l) : T x T LIST -> Bool - returns true if 'e' is the maximum element in the list, false otherwise

```

Prove by structural induction that :

```
max?(e, l) -> max?(e, unique(reverse(l))) || max?(e, repeated(reverse(l)))

```

I've managed to simplify this to :

```
max?(e, l) -> max?(e, unique(l)) || max?(e, repeated(l))

```

But I don't see how to proceed towards proving what is asked...

Used definitions of functions:

```
    unique([]) = []
    unique([e]) = [e]
    unique(cons(e, L)) = cons(e, unique(L)), if member(e, L) = false unique(cons(e, L)) = unique(L), if member(e, L) = true

    repeated([]) = []
    repeated([e]) = [e]
    repeated(cons(e, L)) = cons(e, repeated(L)), if member(e, L) = true unique(cons(e, L)) = unique(L), if member(e, L) = false

    reverse([]) = []
    reverse([e]) = [e]
    reverse(cons(e, L)) = append(reverse(L), [e])

    also,
    member : Element x List -> Bool
    member(e, []) = false
    member(e, [a]) = (e == a) (true, if a is equal to e; false, if a isn't equal to e)
    member(e, cons(a, L)) = (e == a) V member(e, L) (V is logical disjunction)

    append : List x List -> List
    append([], L) = L
    append([e], L) = cons(e, L)
    append(cons(e, L1), L2) = cons(e, append(L1, L2))

```

# Answer
> 2 votes
*Note:* I mixed up boolean functions and propositions in what follows for brevity, and I hope it'll not cause any confusion.

I assume you have defined the function $\max?$ something like this:

```
max?(e, l) = ge_all?(e, l) && member(e, l),

```

where

```
ge_all?(e, []) = True
ge_all?(e, cons(x,xs)) = e >= x && ge_all? e xs.

```

You will need a bunch of lemmas \[they can be proved using structural induction\]:

**Lemma 1:** $\text{member}(e, l) \implies \text{member}(e, \text{unique}(l)) \vee \text{member}(e, \text{repeated}(l))$ \[this one is suggested by @Alexander\]. Its proof is pretty boring because of lots of subcases.

**Lemma 2:** $\text{ge\_all?}(e, l) \implies \text{ge\_all?}(e, \text{unique}(l))$.

**Lemma 3:** $\text{ge\_all?}(e, l) \implies \text{ge\_all?}(e, \text{repeated}(l))$.

**Theorem:** $\max?(e,l) \implies \max?(e, \text{unique}(l)) \vee \max?(e, \text{repeated}(l))$.

**Proof sketch**:

$\max?(e, l)$ implies $\text{member}(e,l)$, which in its turn implies $\text{member}(e, \text{unique}(l)) \vee \text{member}(e, \text{repeated}(l))$ \[by lemma 1\]. So we consider two cases: (1) $\text{member}(e,\text{unique}(l))$ and (2) $\text{member}(e,\text{repeated}(l))$.

In the case (1) we can prove $\text{max?}(e,\text{unique}(l))$ like this: $\max?(e, l)$ implies by definition $\text{ge\_all?}(e,l)$, which \[by lemma 2\] implies $\text{ge\_all?}(e,\text{unique}(l))$. Since $\text{ge\_all?}(e,\text{unique}(l))$ and $\text{member}(e,\text{unique}(l))$ we get $\text{max?}(e,\text{unique}(l))$.

The case (2) is similar. End of proof.

# Answer
> 1 votes
Probably you can show that

```
member (e, l) = member (e, unique (l)) || member (e, repeated (l))

```

Then maximum element it's either among unique elements or among repeated.

---
Tags: correctness-proof, induction, proof-assistants
---


# Question
Title: MIS complexity in cubic triangle-free graphs
The question Complexity of Independent Set on Triangle-Free Planar Cubic Graphs asks for the complexity of the independent set problem in triangle-free planar cubic graphs. In the statement of the question Independent set on cubic triangle-free graphs, it is claimed that a more general problem - maximum independent set in triangle-free cubic graphs (not necessarily planar) - is NP-complete. Could you please provide a reference to the paper for that result?

(Note that the answer to the first of the mentioned questions provides a paper where MIS is shown to be NP-hard in triangle-free planar graphs with vertices of degree \<= 3, and I am asking for 3-regular graphs.)

**Update**: There has appeared a new answer in there since, and it addresses this question as well. The note "NP-complete problems on a 3-connected cubic planar graph and their applications" by Ryuhei Uehara contains a proof that MIS is NP-complete for cubic, planar, and 3-connected graphs of girth greater than 3.

# Answer
The paper "The Vertex-Disjoint Triangles Problem" (http://link.springer.com/chapter/10.1007/10692760\_3) by Guruswami et al. has the proof of its NP-completeness as Theorem 3.

**Update**: As stated in a more recent answer to Complexity of Independent Set on Triangle-Free Planar Cubic Graphs, there is a note "NP-complete problems on a 3-connected cubic planar graph and their applications" by Ryuhei Uehara that contains a proof that MIS is NP-complete for cubic, planar, and 3-connected graphs of girth greater than 3.
> 3 votes

---
Tags: complexity-theory, reference-request, np-complete, reductions
---


title: Difference between 2f+1, 2f and 3f+1

text:
# Question
Title: Difference between 2f+1, 2f and 3f+1
I am currently reading the Practical Byzantine Fault Tolerance paper. I am unable to completely understand the difference between `2f` and `2f+1`. If `2f+1` means that a majority of the nodes are non-faulty then what does `2f` represent?

# Answer
$2f$ and $2f + 1$ are just numbers. A set of $2f + 1$ nodes has a majority of non-faulty nodes, as you say; a set of $2f$ nodes can be deadlocked between the non-faulty and faulty nodes. A total of $3f + 1$ nodes are needed in the system to be able to construct a set of $2f + 1$ nodes when up to $f$ nodes are not responding (as outlined in section 3).
> 3 votes

---
Tags: distributed-systems, computer-networks
---


title: Big O Algorithm Analysis

text:
# Question
Title: Big O Algorithm Analysis
I'm confused about the complexity of the following code:

```
for(i=1; i<=n; i = 2*i)
     for(j=1; j<=i; j++)
        print A[j]

```

I know that the first loop is logn, but I'm confused on what the second for loop would be since j is bound to i. Is this simply O(logn)?

I've plotted out the output as follows and thought it would be O(nlogn):

Assuming n = 8 or higher

```
i=1  j=1
i=2  j=1,2
i=4  j-1,2,3,4
i=8  j=1,2,3,4,5,6,7,8

```

# Answer
The number of iterations for the outer loop is $\lfloor \log n \rfloor$. The number of iterations for the inner loop is $i = 2^k$, where $k$ is the number of current iteration of the outer loop. So the number of computational steps is proportional to $$\sum\_{k = 0}^{\lfloor \log n \rfloor}{2^k} = 2^{\lfloor \log n \rfloor + 1} - 1.$$ Using the following inequality $$n - 1 \< 2^{\lfloor \log n \rfloor + 1} - 1 \< 2n,$$ one can get that the time complexity of the algorithm is $\Theta(n)$.
> 9 votes

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


title: Lambda Calculus Reduction Examples

text:
# Question
Title: Lambda Calculus Reduction Examples
I'm still trying to get the hang of lambda calculus:
I completed simplified some of these already but am lost on the last two. I did so far: \begin{align\*} (\lambda x.x)y &\to y\\ (\lambda x.y)x &\to x \end{align\*}

However, I'm not sure how to simplify these two:

\begin{gather\*} (\lambda x.x y)(\lambda y.y z)\\ (\lambda x.x y)(\lambda a.a b) p \end{gather\*} They are a little bit similar, but I'm not sure how to simplify these expressions.

# Answer
> 6 votes
Just follow the rules of $\beta$-reduction and remember that function application associates to the left, i.e. $f g h$ is just syntactic sugar for $(f g) h$.

I'll show the steps for $(\lambda x.x y)(\lambda y.y z)$.

1. Strip off $\lambda$ from $(\lambda x.x y)$. You get the abstraction body $x\ y$, where $x$ is free now.
2. Substitute the argument $(\lambda y.y z)$ for $x$ into $x\ y$: $(\lambda y.y z)$ y. Notice that I didn't do anything with $y$ during this step.
3. Observe that the current $\lambda$-term is an application that can be reduced further. Again stripping off $\lambda$ we get $y\ z$ and substituting $y$ for $y$ results in the same term $y\ z$.

Here is the sequence of $\beta$-reductions without the intermediate steps: $$(\lambda x.x\ y)(\lambda y.y\ z) \rightarrow\_\beta (\lambda y.y\ z) y \rightarrow\_\beta y\ z.$$

The second problem can be dealt with in the same way.

---
Tags: lambda-calculus
---


title: CNOT, Hadamard and Φ quantum gates

text:
# Question
Title: CNOT, Hadamard and Φ quantum gates
How can somebody use these gates to create other gates like pauli's or other gates? Also how can somebody go from pauli's to CNOT, Hadamard and Φ quantum gates?

# Answer
This is actually kind of complicated. Basically you can:

* Decompose a huge multi-qubit operation into many single-qubit gates, but with lots of controls allowed on each single-qubit gate. Think of it as doing Gaussian elimination: you're factoring the matrix into a bunch of simple row operations.
* Gradually reduce the number of controls to at-most-one-per-gate, by repeatedly using a construction based on the fact that every operation has a square root and an inverse.
* Factor each single-qubit operation $U$ into $A$, $B$, $C$, $\theta$ such that $ABC = I$ but $AXBXC e^{i \theta} = U$. Use that to replace controlled-$U$ gates with uncontrolled single-qubit operations separated by $CNOT$ gates.
* Approximate each uncontrolled single-qubit operation with a sequence of $H$ and $T$ gates (which is possible because they correspond to rotations that can approximate any other rotation).

What you're left with is a circuit containing only $CNOT$, $H$, and $T$ gates that approximates the original operation. You need more gates to get a better approximation, but you can get as close as desired. Also the overhead isn't *too* terrible.

For details of the constructions, and proofs that the errors don't compound in a way that destroys the efficiency of the approximation, you'll probably have to get a textbook or read papers. There's a *lot* of details.
> 4 votes

---
Tags: quantum-computing
---


# Question
Title: Relation and difference between information retrieval and information extraction?
From Wikipedia

> **Information retrieval** is the activity of obtaining information resources relevant to an information need from a collection of information resources. Searches can be based on metadata or on full-text indexing.

From Wikipedia

> **Information extraction (IE)** is the task of automatically extracting structured information from unstructured and/or semi-structured machine-readable documents. In most of the cases this activity concerns processing human language texts by means of natural language processing (NLP). Recent activities in multimedia document processing like automatic annotation and content extraction out of images/audio/video could be seen as information extraction.

What are the relations and differences between information retrieval and information extraction?

Thanks!

# Answer
> 12 votes
**Information retrieval** is ***based on a query*** \- you specify what information you need and it is returned in human understandable form.

**Information extraction** is about structuring unstructured information - given some sources ***all of the (relevant) information*** is structured in a form that will be easy for processing. This will not necessary be in human understandable form - it can be only for use of computer programs.

Some sources:

# Answer
> 8 votes
http://gate.ac.uk/ie/ gives a very nice, concise distinction:

> Information Extraction is not Information Retrieval: Information Extraction differs from traditional techniques in that it does not recover from a collection a subset of documents which are hopefully relevant to a query, based on key-word searching (perhaps augmented by a thesaurus). Instead, the goal is to extract from the documents (which may be in a variety of languages) salient facts about prespecified types of events, entities or relationships. These facts are then usually entered automatically into a database, which may then be used to analyse the data for trends, to give a natural language summary, or simply to serve for on-line access.

To put it pictorially:

> Information Retrieval gets sets of relevant documents:
>
> Information Extraction gets facts out of documents:

# Answer
> 2 votes
**Information retrieval** is about returning the information that is relevant for a specific query or field of interest. Note that this information could also be in the form of general documents, sure enough search engines are a notable example of such task. I would say that the most important entities recognizable for information retrieval are the initial set of documents/information and the query that specify "what to search for".

On the other hand **information extraction** is more about extracting (or inferring) general knowledge (or relations) from a set of documents or information. Note that here all the content of the documents could be considered as a whole corpus of data from which extract the knowledge. Of course also for this case you can somehow specify what do you want to extract, but it is more about **properties/relations** than specific subjects/topics. Properties are more domain-specific, while generally relations cover more generic scenarios.

Again, with search engines you're asking to get the sites that are most likely to contain information about that specific subject. This is an example of **information retrieval**.

For **information extraction** you could instead, for example, ask to extract all the names of cities, or e-mail addresses, that appear in a corpus of documents. You could even go much more generic, asking simply to extract knowledge. As you can see this is really generic, but it can be accomplish, for example, by obtaining triplets of the form subject-action-object for each valid sentence of a text (this is best suited for natural language texts).

If you're interested these (and other) topics are explain in details in the Natural Language Processing chapter of the book Artificial Intelligence: A Modern Approach.

# Answer
> 2 votes
From a modeling standpoint, information retrieval is a deep field predicated on several disciplines, including statistics, math, linguistics, artificial intelligence and now data science. In practice, these models are applied against text within corpora to discover patterns in the data. Not only do the IR models overlap in their usage, they can "partner" with other models such as k-means or k-nearest neighbor models, then other models can be applied from the vantage point of computational linguistics such as LDA/LDI and topic modeling Then, the end game is some sort of information visualization of this discovery--after ranking, clustering and aggregating work. Information Retrieval may appear to be a cryptic discipline, but serious effort, which is greatly appreciated, is going into opening up the area for deeper understanding of each model, and the interaction between models. I cite "Synthesis Lectures on Information Concepts, Retrieval, and Services" Series as the best place to delve into a foundation for IR.

While I don't entirely separate IR and Information Extraction, perhaps a subset of IE, concept level extraction, does apply IR patterns along with AI-based inferencing rules to extract related ontologies. The graphical nature of these relations are being enhanced with ontology modeling in OWL and RDF, and with graph databases, which allow for a less strict or rigorous set of relationship modeling, and allow for more relationships to surface, rather than being controlled per se. The ability to grow information extraction dynamically keeps its "discipline" strongly interesting to researchers.

Both IR and IE play out in our own significant "entities of the moment"--some have called "dynamic ontologies"--some being Palantir-- we need the patterns, models, simulations and visualizations of those significant entities to do business in the face of morphing new sources of information and changing of existing information. The conceptual, relational, definitional, pattern and ontological modeling have to be flexible and their visualizations the same. The heavy lifting of AI engines such as Watson in the information extraction and inferencing fields has cast a spotlight on the IE and frankly IR fields. Also the ubiquity of natural language processing and machine learning are calling attention to IR and IE models and engines. The impact of IR models on search and SEO, and on semantic web modeling is one of those "watching a change agent change due to impacts back from what it impacted" events--somewhere in harmonics and relativity theory. IR and IE are expanding based on what they're impacting.

---
Tags: data-mining, natural-language-processing
---