title: Defining a new operator in CTL

text:
# Question
Title: Defining a new operator in CTL
Lets consider a new operator $B$ where $a B b$ means "in every execution, if $b$ holds some time, then $a$ does so before it" and we're asked to define it in CTL.

My working: the system can only fail if $b$ holds. If $b$ doesn't hold, we're in the clear - so one possible path could be $(¬ □ b)$. The only other path that could hold is one where $a$ happens before $b$, so $(a$ $U$ $b)$ is another path. Overall we're left with $∀((a U b) ∨ (¬ □ b))$. For every path either $a$ happens before $b$ OR $b$ never happens.

Is the way I reasoned about this question correct? Are there any holes in my logic that I should re-consider? Please reply as a comment if possible, and many thanks in advance for any input.

# Answer
> 1 votes
For the answer $\forall \lnot \exists \left( \left( \lnot a \right) \bigcup b \right)$:
I think you have got the right idea. However, this formula is not in CTL since $\lnot \exists \left( \left( \lnot a \right) \bigcup b \right)$ is not a path formula.

By $\forall \lnot \exists \left( \left( \lnot a \right) \bigcup b \right)$, I think you want to say $\forall \Box \left( \lnot \exists \left( \left( \lnot a \right) \bigcup b \right) \right)$, which is the answer.

(If you are observing the system from the very start (i.e., its initial state), the simpler and weaker one $\lnot \exists \left( \left( \lnot a \right) \bigcup b \right)$ would be also acceptable. Please check it and let me know whether it is right.)

As I have mentioned in the comment, there are past CTLs (PCTL) which incorporate *past* operators facilitating the expression of "time going backwards". Using PCTL (for example in \[1\]), your property can be directly rendered by $\forall \Box (b \implies \Diamond^{-1} a)$ (Note its syntax!). You can guess the meaning of $\Diamond^{-1}$ easily.

\[1\] Specification in CTL+Past for Verification in CTL (2000)

---
Tags: logic, model-checking, temporal-logic, computation-tree-logic
---


# Question
Title: 4-bit input, 5-bit output, logical right shift by 2, which is the correct set of 5 output bits?
Suppose I have the following inputs:

1110
1111

If I perform a logical right shift by 2 on each, are the 5-bit outputs these:

00111
00111

or these:

01110
01111

If it's neither, then I'd appreciate an explain why and what I've done wrong!

# Answer
There are two ways to do a shift: either the "new" digit (the leftmost, msb) is set to zero, or it is set to the digit that was there before. The former is usually called *logical shift* while the latter preserves the sign of the number (in case you use the complement representation) and is called *arithmetic shift*. But sometimes both are just called shift, and one needs to clarify the desired behavior.

Since you as about buffers of length 5 bits, the msb is anyway 0 so logical shift-arithmetic shift, and I'd say the 2-bit right shift is:

```
01110  -> 00111 -> 00011
01111  -> 00111 -> 00011

```
> 2 votes

---
Tags: boolean-algebra
---


# Question
Title: Rounds in communication complexity - definition
What does rounds in communication complexity mean in setting of deterministic/non-deterministic $2$ party communication or multi party setting?

Is it number of bits exchanged between players participating/involved?

In multiparty setting what does simultaneous and non-simultaneous messaging means? Is it related to round?

# Answer
The notion of round should be quite similar to the intuitive idea of "one step of the protocol". At any round you are allowed to send 1 message (of any size) and/or receive one message. The message you send at round $i$ may depend on all the information you have up to round $i$, but it **cannot** depend on the message you receive at round $i$ (or later). It follows that any information that depends on the the message you receive at round $i$ may be sent only at round $\ge i+1$. This sequentiality is the core of splitting into rounds, they just formulate the causality of the protocol

Since the above doesn't determine the size of each message sent, one can define the *communication complexity* to be exactly the number of bits communicated throughout.

As for simultaneous transmission of messages: In the above informal description I wrote:

> At any round you are allowed to send 1 message (of any size) and/or receive one message.

note the `and/or` part. If simultaneous transmission is allowed, then each party sends a message **and** receives one. If no simultaneous messages allowed, then the party either sends or receives a message, but not both. This makes the partitioning to rounds more crisp: every time the sender party changes, it is a new round.

finally, I repeat the recommendation of @hengxin, and refer you to the book of Kushilevitz and Nissan.
> 2 votes

# Answer
*Round:* The protocol (or the communication game) proceeds in rounds. In each round, some bits are communicated. In the simple model of Alice and Bob to evaluate some function f, it depends on the protocol P that specifies which player sends a bit of communication (and of course, what bit to send) next.

*Complexity measure:* The communication complexity refers to the number of bits communicated.

*Simutaneous:* Simultaneous protocols were defined in the paper "Simultaneous Messages vs. Communication" \[1\].

> We consider a restricted version of the multiparty communication game which we call the *simultaneous messages model*. The difference is that in this model, each of the $k$ players simultaneously sends a message to a referee, who sees none of the input. The referee then announces the function value.

---

*Note:* The answer above is by no means formal and rigorous. For the mathematically precise answer, please refer to the book "Communication Complexity" by Eyal Kushilevitz and NoamNisan.

\[1\] Simultaneous Messages vs. Communication. Babai, Kimmel, and Lokam 1995
> 1 votes

---
Tags: communication-protocols, communication-complexity
---


# Question
Title: Solving a recurrence relation using Divide and Conquer Master Theorem
For the recurrence relation

$$T(n) = 16T(n/4) + n!\\,,$$

I have found that $T(n)\in Θ(n!)$. Can this be deduced using the Master Theorem?

# Answer
> 1 votes
Yes. Recall that the Master Theorem deals with recurrences of the form $$ T(n) = a\cdot T\left(\frac{n}{b}\right)+f(n) $$ In your particular case you have $a = 16$, $b=4$ and $f(n) = n!$.

Then we decide the complexity by comparing $f(n)$ to three functions of $n$, $a$ and $b$ (really we compare it basically the same function, with a $\log$ wiggle room, but in different ways).

In particular the third case holds where $f(n) \in \Omega(n^{c})$ where $c \> \log\_{b}a$. You have that $\log\_{b}a = \log\_{4}16 = 2$, so you have to prove (or at least convince yourself, depending on how rigorous you're being) that $n! \in \Omega(n^{c})$ for some $c \> 2$.

It should be reasonably clear that you can pick any constant $c$ in this instance, and that this case holds. As it does, we get immediately (which is of course the point of the Master Theorem) that $T(n) \in \Theta(f(n))$, which in this case gives $T(n) \in \Theta(n!)$.

---
Tags: asymptotics, recurrence-relation, master-theorem
---


# Question
Title: Efficiently count frequency of n-grams at start of words
I have a text file with all possible 5-grams (26^5 = 11.881.376) organized in rows as:

aaaaa
aaaab
aaaac
aaaad
.....

and I have a txt file (organized in rows) with all English words. I have to find how much time every 5-gram is at the beginning of a word. I'm using this code:

```
def frequency(five-grams, dict):
    result = {}

    for gram in five-grams:
        freq = 0
        for word in dict:
            if word.startswith(gram):
               freq = freq + 1

        result[gram] = freq

    return result

```

However this method takes too long (after hours the algorithm is still running). Is there a more efficient and faster method?

# Answer
There is a 11.881.376 times faster method. Instead of for every 5-gram looping over the entire dictionary, loop over the dictionary once, and for every word determine with what 5-gram it starts and then increment the counter for that particular 5-gram.
> 4 votes

---
Tags: algorithms, algorithm-analysis, search-algorithms, strings, search-problem
---


# Question
Title: Direction of restriction for NP hard proves
I have a very silly question, as I am reading through all the proofs showing a problem is NP hard, one of the techniques is by showing an already-proven NP complete problem is a special case for that problem.

I am wondering shouldn't that be another way around? I mean if you show your problem is a special case of a NP-complete problem, then you showed it is NP complete as well? I know this logic is wrong but why?

What is the advantage and disadvantage of this technique.

Comment: this question actually contents the answer for why we need to reduce a problem to a NP hard problem to prove its NP hardness.

# Answer
> 2 votes
The technique your top paragraph shows NP-hardness. The technique in your next paragraph shows membership in NP.

# Answer
> 2 votes
as @Ricky Demer suggested, the restriction only shows you the NP-hardness, you also needs to show the problem belongs to NP in case to you want tho show the NP-completeness.

This answer is dedicated to answer your questions in your comment to Mr. Ricky's answer.

To show some problem is NP-hard, you need to prove worst case scenario is NP hard.

If you can show a NP hard problem is a special case for the problem you want to prove, then it that problem is also NP-hard. Because this special case showed the worst case is at least NP hard.

Of course there might be other cases in a NP hard problem that can be solved in polynomial time, but those are not the worst cases.

So regardless of the relation between P and NP, restriction is correct.

The technique you showed in your 2nd paragraph is not sufficient, Because as what I wrote in the previous paragraph, the problem you need to prove can be a case solvable in P as well, hence you cannot say it is NP-hard.

In addition, as long as you can find a proven NP hard special case for your problem, and the proof is easier than reduction or any other method, then it is a good idea to use restriction.

From RandomStudent: the reduction actually works in a similar way.

Have fun with cs :)

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


# Question
Title: Create CFG and pushdown automaton for {ww}
I've been trying to make a CFG, a pushdown automaton and a regular expression for the language

$\qquad L(M) = \\{ww : w \in \\{a, b\\}^\*, |w| \text{ is even}\\}$.

I understand how the reverse of the string work, that is

$\qquad L' = \\{ ww^R : w \in \\{a, b\\}^\*\\}$,

what i am asking for is to do it this way , i have already solved (L') : http://i921.photobucket.com/albums/ad53/Johann\_1990/IMG\_20150117\_132616.jpg

but is there is a way to solve this one too?
$\qquad L(M) = \\{ww : w \in \\{a, b\\}^\*, |w| \text{ is even}\\}$.

For example, $abaaba \in L$ with $w = aba$.

# Answer
> 1 votes
You can not do so as $L$ is not context-free.

See our reference questions for how to prove that, i.e.

---
Tags: formal-languages, context-free, regular-languages, pushdown-automata
---


title: Solving recurrence relation

text:
# Question
Title: Solving recurrence relation
I am trying to find a $\Theta$ bound for the following recurrence equation:

$$ T(n,p,k)=T(n,p,k/2)+T(n,p/4,k)+T(n/8,p,k)+npk $$

```
                   npk
    /               |                 \
   /                |                  \
T(n,p,k/2)    T(n,p/4,k)     T(n/8,p,k)

```

the max height of the recursion tree is $ \log\_{8}n $ and the cost of each level is at most npk so i guess the answer is $\Theta (npk \log\_{8}n) $

Is my answer right?

# Answer
The cost at each level isn't $npk$. Let's look at the first few levels.

1. The cost at the top level, $l=0$, is indeed $npk$.
2. At the next level ($l=1$) you have three recursive calls: $T(n,p,k/2)$, $T(n,p/4,k)$, and $T(n/8,p,k)$ with costs $npk/2, npk/4, npk/8$ for a total cost at level two of $$ \frac{npk}{2}+\frac{npk}{4}+\frac{npk}{8}=npk\cdot\frac{7}{8} $$
3. At the subsequent level you have nine recursive calls and if you do a bit of arithmetic you see that the total cost at that level ($l=2$) is $$ npk\cdot\left(\frac{7}{8}\right)^2 $$
4. You can show inductively that the cost at level $l$ will be $$ npk\cdot\left(\frac{7}{8}\right)^l $$ so the total cost up to and including level $M$ will be $$ T(n,p,k)=\sum\_{l=0}^Mnpk\cdot\left(\frac{7}{8}\right)^l=npk\cdot\frac{1-(7/8)^{M+1}}{1-7/8}\<8npk $$ since, as $M$ increases $(7/8)^{M+1}\rightarrow 0$. In other words, $T(n,p,k)=O(npk)$

It's clear that $T(n,p,k)\>npk$, since that's the contribution at level zero, so we have, finally, $T(n,p,k)=\Theta(npk)$.
> 0 votes

---
Tags: time-complexity, recurrence-relation
---


title: Definition of $D^P$?

text:
# Question
Title: Definition of $D^P$?
What is the definition of the complexity class $D^P$?

In recent papers I sometimes read $D^P$ but could not find a definition of it. Unfortunately Complexity Zoo does not give one, too.

Is it the same as: "A language L is in the class $DP$ if and only if there are two languages $L\_1\in NP$ and $L\_2\in coNP$ such that $L = L\_1\cap L\_2$" (Def. 17.1 from Papadimitriou - Computational Complexity (1994))?

Note: In the stated definition it says $DP$ not $D^P$. But I was wondering if it is the same.

# Answer
The class $\mathsf{D^p}$ was originally introduced in the context of studying the facets of the traveling salesman polytope. It contains all languages that can be considered as the intersection of a language in $\sf NP$ and one in $\sf co\text{-}NP$. Formally, $\mathsf{D^p} = \\{ L\_1 \cap \overline{L\_2} \mid L\_1,L\_2 \in \mathsf{NP} \\}$. It first appeared in \[1\].

---

\[1\] Papadimitriou, Christos H., and Mihalis Yannakakis. "The complexity of facets (and some facets of complexity)." Journal of Computer and System Sciences 28.2 (1984): 244-259.
> 4 votes

---
Tags: complexity-theory, complexity-classes
---


# Question
Title: Selection, crossover and mutation function choice in genetic algorithms
I have been developing a GA for one of the projects I'm working on. I have everything implemented with no problems and I really like how GAs work in general, it's a really cool and relatively new concept. However I'm wondering which specific algorithms I should use for selection, crossover and mutation.

I understand that it often depends on what your data type is, for example individuals who's chromosome order is important should use crossover algorithms listed on this Wikipedia article (with maybe a few more to be added to that list), but how do I choose between them? What should I consider when I am selecting which algorithms to use for these three things?

Currently I have implemented Tournament selection, partially matched crossover and index shuffling for mutation and this gives me the exact output I want, but how do I know these are the best choice for my problem.

(P.S. This is purposefully as abstract as possible, I'm not looking for an answer to my specific problem but more how anybody can go about choosing which algorithms are best for their particular situation.)

# Answer
> 2 votes
(TL;DR - see table at the end)

After several days of reading academic papers, I have came to one simple conclusions: **everything** is problem specific.

My advice to anybody reading this for the answer is test, test and test. Not just different methods of selection, crossover and mutation; but also different combinations.

I have been using the DEAP python library to implement my GA, so I have been restricted to the methods they have already implemented in their source code (I plan to spend a fair amount of time contributing to that library to increase the options they have once I have finished my current project, it really is great) but it made writing the GA much faster and swapping out different selection, crossover and mutation functions much much easier. On those grounds I would recommend using something like this if possible to figure out what methods are best for your problem.

I ran all possible combinations of viable methods (some methods as I said in the question are specific to chromosomes where the order is important) and recorded time taken and final solution fitness (this the score my objective function gives the final solution the GA outputs); and from this I chose which was my best combination.

However, nobody wants a "go figure it out for yourself" answer, so I have provided a table that show how long (in relative time) different crossover algorithms took to "solve" (by this I mean give an answer to) a 20-city Hamilton path problem.

Poon, P. W., & Carter, J. N. (1995). Genetic algorithm crossover operators for ordering applications. Computers & Operations Research, 22(1), 135-147.

I also encourage you to read that paper, it helped me a lot regarding crossover choice, but bare in mind that methods will vary from problem to problem. It unfortunately is a trial and error thing as there is no "choose X, Y and Z methods" solution.

# Answer
> 2 votes
**SELECTION**. Different types of selections will have different advantages and disadvantages. You will mostly find the right one through trial and error.

**CROSSOVER**. The optimal crossover technique is usually problem-specific. A general rule is to avoid using a single point crossover, as suggested by this paper.

**MUTATION**. Some mutation guidelines are provided in this paper.

---
Tags: algorithms, genetic-algorithms
---


# Question
Title: Quantum computers and computable functions
A quantum computer can possibly calcluate computable functions faster, but it can't calculate functions which a normal computer can't calculate?

If a function is not computable? Does this mean it will never be computable? Even if we change the axioms which our mathematical system is based on or we find a contradiction in it? Are we never be able to find something in the universe which can calculate these functions?

Is that right?

# Answer
> 8 votes
You are correct, a quantum computer defined *properly*: with a finite gate set and rational (you can relax this to algorithmic, but that can be bit circular) transition probabilities will get you only the computable (by a classical Turing machine) functions. Although it might compute them faster than a classical computer.

To get a hyper-computer (something that computes functions that are not computable by a classical Turing machine), you need to sneak something that usually feels 'non-finitary' into the model -- the most common suspect is a non-computable real number -- which your model then extracts its power from. You can make these sort of models of computation from modifying classical *or* quantum systems. If I recall correctly, the first definitions of quantum TMs were actually accidentally hyper-computing because they allowed non-algorithmic phases in their operators.

To turn to your last question of "Does this mean it will never be computable?", what you are asking about is the Church-Turing thesis. It states, in its vaguest form, that anything that is computable is computable by a Turing Machine. Most people believe this thesis.

> Even if we change the axioms which our mathematical system is based on or we find a contradiction in it?

Here you are asking about Kleene's variant of the Church-Turing thesis. Since the CT-thesis cannot be 'proven' (we can always continue to disagree about the first 'computable' in the vague definition), we have to rely on mathematician's beliefs and philosophical discussion. Most mathematicians believe that in any reasonable axiomatic system, any 'finite-feeling' model of computation will be at most Turing-complete.

> Are we never be able to find something in the universe which can calculate these functions?

It is important to note that here you are asking a completely different (but related) question than the previos. You are asking about the physicalist variant of the Church-Turing thesis. Although historically this was not the preferred interpretation of the CT-thesis, from my experience it is now the most common way of reading the thesis. Again, here most computer scientists and physicists familiar with CS believe that all functions computable by machines in the physical world are Turing-computable.

# Answer
> 5 votes
I can make some remarks that might help what you are trying to discuss.

There have already been some mathematically well-defined computational models that can "compute" (define/recognize/etc.) uncomputable languages. For example, there are uncountable many languages defined by probabilistic finite automata with unbounded error \[Rabin, 1963\]. (The cardinality of computable languages/functions is countable.) A similar result was recently obtained for unary languages defined by 2-state quantum finite automata \[Shur and Yakaryilmaz, 2014\].

In the above examples, there is no bound on the error. In the case of bounded-error language recognition, it was shown that bounded-error polynomial-time "algorithms" can compute some uncountable languages (functions) \[Adleman et. al., 1997\] if we allow to use uncountable transitions. (I do not know how we can prove that there is no such transitions in nature.) Moreover, the same result can also be obtain for probabilistic "algorithms" \[see this cstheory question\]. Recently, it was also shown that polynomial-time constant-space quantum Turing machines (two-way quantum finite automata) can recognize some uncountable languages \[Say and Yakaryilmaz, 2014\]. In the same paper, also a proof system was given which can verify the memberships of any language with bounded error.

I believe that there are some other computational models or computational set-up's (etc.) that can do beyond deterministic Turing machines.

---
Tags: computability, quantum-computing, philosophy
---


# Question
Title: Does stay put TM recognizes same languages as standard TM
I am reading this text book and it says that stay put turing machine recognizes the same languages as regular turing machine by just adding transition functions (without adding any new states or symbols). I am trying to figure that out.. But so far, no luck. I think the key here is "recognizes" rather than "decides"? How do i prove this? Thanks

# Answer
No, the key terms are not "recognizes" and "decides", but rather "simulates". Given a Turing machine that can stay put, you can *simulate* it using a Turing machine that doesn't stay put. Given a transition of the form:

* On state $s\_1$, if the symbol under the head is $\alpha\_1$ then change it to $\alpha\_2$, stay put and transition to state $s\_2$

you replace it with a pair of transitions

* On state $s\_1$, if the symbol under the head is $\alpha\_1$ then change it to $\alpha\_2$, move right and transition to $s'$
* For every symbol $\beta$: On state $s'$, if the symbol under the head is $\beta$ then change it to $\beta$, move left and transition to state $s\_2$

Here $s'$ is a new state that is used only to handle this transition.

The new Turing machine doesn't stay put but simulates the original Turing machine.

---

As the OP points out, we can actually improve this simulation by not adding new states at all (except for possibly one more state, a "stuck" state). Suppose we are at state $s\_1$, see the symbol $\alpha\_1$, and stay put. Let us continue to follow the machine. Either the machine never moves away from its spot, or it eventually moves either left or right, transitioning to state $s\_2$ after changing the original symbol to $\alpha\_2$. In the latter case, we can change the transition to a simple transition to $s\_2$. In the former case, we can move instead to a special "stuck" state in which the Turing machine finds itself in an infinite loop; this state can be common for all "stuck" situations.

If we are guaranteed that the original Turing machine never gets stuck, and this is probably the assumption in your textbook, then we can do away with the "stuck" state, so that no new states are needed at all.
> 4 votes

---
Tags: computability, turing-machines, undecidability, turing-completeness
---


title: Regular Grammar and Regular Language

text:
# Question
Title: Regular Grammar and Regular Language
From Wikipedia, Regular Language

> All finite languages are regular.

and Also Regular Grammar, is a way to describe the Regular Language

> Right regular grammar (also called right linear grammar).
>
> Left regular grammar (also called left linear grammar).

From Wikipedia its Example : a\* b c\* can be described as Regular Grammar..

but it generate infinite number of 'a's and infinite number of 'c's.

Recall Regular Language can be described by Regular Expression and Also Finite Language ..

# Answer
> 0 votes
This might be a language issue. In (mathematical) English, the statement *all finite languages are regular* means: **if** $L$ is a finite language **then** $L$ is regular. No implication in the other direction ("if a language is regular then it is finite") is implied.

---
Tags: automata, formal-grammars
---


# Question
Title: Create cfg and npda/pda for Language {ww}
I've been trying to make a CFG, and npda/pda for this language (to construct an npda for accepting the language):

L(M)={ww:w∈{a,b}∗,|w| is even}.

i had already solved the reverse of the language (like this):

L′={wwR:w∈{a,b}∗},

Please check this snapshot to know what i am asking to do ! (L') : http://i921.photobucket.com/albums/ad53/Johann\_1990/IMG\_20150117\_132616.jpg

but is there is a way to solve this L(M)={ww:w∈{a,b}∗,|w| is even}?

For example, abaaba∈L with w=aba.

Note that I'm not asking to prove by conduction or anything else.

# Answer
Short answer: $L$ is not context-free, so there is no CFG/PDA.
> 4 votes

---
Tags: context-free, pushdown-automata
---


# Question
Title: The number of operations of Explicit and Implicit Euler for 1D hear equation
I'm studying with "Numerical Solution of Partial Differential Equations by K.W.Morton and D.F.Mayers". On page 25, it says "2(add) + 2(multiply) operations per mesh point for the explicit algorithm (2.19)", but it seems 3(add) + 2(multiply) to me, how did I get wrong?

(2.19) $U\_j^{n+1}=U\_j^{n}+\mu(U\_{j+1}^{n}-2U\_j^{n}+U\_{j-1}^{n})$

My counting is

2(add) and 1(multiply) inside the bracket

1(multiply) for $\mu$ and the brackets

1(add) for $U\_j^{n}$ and the rest

# Answer
> 2 votes
Note that

$U^n\_j + \mu (U^n\_{j+1}-2U^n\_j+U^n\_{j-1}) = (1-2\mu)U^n\_j+\mu(U^n\_{j+1}+U^n\_{j-1})$

$1-2\mu$ may be precomputed.

---
Tags: complexity-theory, numerical-algorithms
---


# Question
Title: Can parallel downloading with many ip's possible?
I am not too intelligent,but i got this in my mind.Lets say i download a file from abc.com and the speed is limited for an IP(say 60kbps).Can i initiate parallel downloads from multiple ip addresses which could be virtual IP's OR two diff.devices and break my download into parts,download each part at 60kbps and then join all.So that now it takes less time?IS this possible some kind of software to create Virtual Ip addresses?Or in multiple devices?

# Answer
> 1 votes
If the limitation is coming from the site, then it depends if the server allow you to resume partial downloads. If yes you can have two devices, one downloads the first part of the file, and the second one downloads the second part (telling the server it has already the first part).

The IP-address is given to you by your internet provider and it is unique. So you only have one and it can't be changed with software. (unless sometimes when you restart your router you can have a different one, but you can only have one at a time).

The device which downloads the second part needs to be connected to a network with a different ip-adress (for example your neighbor's Wlan).

But i don't think this is very practical.

---
Tags: communication-protocols, protocols
---


title: Regular and not Regular Grammar

text:
# Question
Title: Regular and not Regular Grammar
According the Peter Linz Book, am a confusing about the two example the Grammar G1 = ({S},{a,b},S,P1) with P1 given as

S -\> abS|a

and G2 = ({S,S1,S2,},{a,b},S,P2)

S -\> S1ab S1 -\> S1ab|S2 S2 -\> a

G1,G2 is regular..

i generated from G1 Language= {ababa,...} and it Regular expression (ab)*a and from G2 = {aabab} is that right it regular expression a(ab)* in the book it show its aab(ab)\* but how

First, is it write regular expression ?? Why this G3 = ({S,A,B},{a,b},S,P) with Production

S -\> A A -\> aB | 'epsilon' B -\> Ab

is not regular ? although its left or right linear prodcution.

second why G3 is not regular ?

# Answer
Consider $G\_1$. Strings generated by this grammar could be derived by repeated use of the production $S\rightarrow abS$ followed by one use of $S\rightarrow a$ to eliminate the variable $S$. Consequently, we can generate strings in the language by repeatedly adding $ab$ to the right and ultimately stopping by adding an $a$ to the right: $$ S\Rightarrow ab\color{red}S\Rightarrow ab\color{red}{abS}\Rightarrow abababS\Rightarrow\dotsm (ab)(ab)(ab)\dotsm a $$ so we generate strings of the form $$ \underbrace{ab\ ab\ \dotsc ab}\_{\text{$0$ or more}}\ a $$ which corresponds to the regular expression $(ab)^\*a$, so $L(G\_1)$ is regular. Note that $G\_1$ is a regular grammar, since it's a *right-linear* grammar, namely one for which all the productions are of the form $A\rightarrow xB$ or $A\rightarrow x$ where $A, B$ are variables and $x$ is a string of terminals.

---

Grammar $G\_2$ is only slightly more complicated. We now have four productions

1. $S\rightarrow S\_1ab$
2. $S\_1\rightarrow S\_1ab$
3. $S\_1\rightarrow S\_2$
4. $S\_2\rightarrow a$

Now a string of terminals can only be generated by production (1) adding $ab$ to the left (since the grammar is left-linear), followed by zero or more productions (2) adding another $ab$ to the left, followed by production (3) and then production (4) adding $a$ to the left. We then can generate strings $$ a\ \underbrace{ab\ ab\ \dotsc ab}\_{\text{$0$ or more}}\ ab $$ In a way similar to the above, a regular expression denoting $L(G\_2)$ could be $aab(ab)^\*$.

---

Your $G\_3$ is not a regular grammar, since in such a grammar, *all* productions must either be right-linear or left-linear. In $G\_3$ the production $A\rightarrow aB$ is right-linear but the production $B\rightarrow Ba$ is left-linear. A regular grammar cannot, by definition, have both right- and left-linear productions.

By the way, $L(G\_3)=\\{a^nb^n\mid n\ge 0\\}$ which you'll soon learn is not a regular language.
> 2 votes

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


# Question
Title: QuickSort Dijkstra 3-Way Partitioning: why the extra swapping?
Given the algorithm above (taken from the slides (p. 35) of the Coursera course “Algorithms Part I” by Robert Sedgewick and Kevin Wayne), look at the scenario where i is at "X", the following happens:

**Scenario:** i -\> "X", "X" \> "P"

```
1. swap("X", "Z"), gt--;   // the value at i is now "Z", which is still > "P"
2. swap("Z", "Y"), gt--;   // the value at i is now "Y", which is still > "P"
3. swap("Y", "C"), gt--;    // Now we finally get a value at i "C" which is < "P"
// Now we can swap values at i and lt, and increrement them
4. swap("P", "C"), i++, lt++;

```

Why don't we just decrement gt until gt points to a value that is \< the value at lt ("P" in this case), then we swap this value with the value at i. This will save swapping operations.

So if we do that for the scenario mentioned above, we'll do:

```
1. gt--
2. gt--
3. swap("X", "C"), gt--;
// Now we can swap values at i and lt, and increrement them
4. swap("P", "C"), i++, lt++;

```

Is this excessive swapping needed for the algorithm? does it improve performance in some way? If it does improve performance, how?

If it doesn't affect performance, please give a proper explanation or a proof as to why this it does not affect performance.

Also, would the second method I mentioned affect performance in any way? please explain why.

P.S. "Affect performance" as used above means either improve/degrade performance.

# Answer
In order to know that you may just decrement `gt`, you have to compare the element at position `gt` to the pivot.

For illustration, here is the relevant part of the code from the slides you took your illustration from:

```
while (i <= gt)
{
   int cmp = a[i].compareTo(v);
   if      (cmp < 0) exch(a, lt++, i++);
   else if (cmp > 0) exch(a, i, gt--);
   else              i++;
}

```

Your modification would look like this:

```
while (i <= gt)
{
   int cmp = a[i].compareTo(v);
   if      (cmp < 0) exch(a, lt++, i++);
   else if (cmp > 0)
   {
      while (a[gt].compareTo(v) > 0) gt--;
      exch(a, i, gt--);
   }
   else              i++;
}

```

If the element is larger, we save a swap, as you illustrated. Furthermore we won't have to compare that element again. If, however, the element is not larger, we will compare it to the pivot twice, once before the swap and once after the swap.

So with your modification we save a swap for each element that is larger than the pivot and on a position that ends up to the right of the pivot, while we introduce an additional comparison for each element in such a position that is not larger than the pivot.

Averaging over all inputs we can expect the number of elements smaller resp. larger than the pivot to be equal. So the performance will depend on the number of elements equal to the pivot (and the cost of a swap vs. a comparison). Your modification will have the better relative performance, the smaller that number is. But 3-way partitioning was developed with inputs with many equal keys in mind, so the original choice seems reasonable.

---

Taking a second look at the modified algorithm, we note that if we compare an element twice, there is no other comparison happening between these two. So it seems worthwhile to remember the result of the comparison. However, if we want to keep the structure of the code, this means a lot of control structure overhead:

```
Boolean doComp = true;
int cmp;
while (i <= gt)
{
   if (doComp) cmp = a[i].compareTo(v);
   doComp = true;
   if      (cmp < 0) exch(a, lt++, i++);
   else if (cmp > 0)
   {
      while (cmp = a[gt].compareTo(v) > 0)
      {
         gt--;
         doComp = false;
      }
      exch(a, i, gt--);
   }
   else              i++;
}

```

My gut feeling is that even though it combines the advantages of the previous two versions in terms of number of comparisons and swaps, it will perform worse due to the overhead of the additional control structures.

Not only have we introduced additional operations (checking conditions, maintaining the flag), we also introduced (compared to Dijkstra's version) two additional conditional jumps (for if and while), that will often but irregularly switch between taken and not taken. The latter is a problem on modern processors, since they rely on branch predictions for optimal performance and such branches will lead to a high number of mispredictions. (The branch corresponding to the outer loop is an opposite example: Always predicting that the loop will be entered is wrong only once.)

With these considerations in mind, we can try to optimize the code. The following should perform quite well:

```
while (i <= gt)
{
   int cmp = a[i].compareTo(v);
   if (cmp > 0)
   {
      while ((cmp = a[gt].compareTo(v)) > 0) gt--;
      exch(a, i, gt--);
   }
   if (cmp < 0) exch(a, lt++, i++);
   else         i++;
}

```

This version makes as many comparisons as Dijkstra's version and as many swaps as your suggested version without introducing too much overhead: For each comparison we have one branch based on `cmp > 0` and possibly one based on `cmp < 0`. This is the same as for Dijkstra's version except that the role of the two comparisons is exchanged.

---

So, summing up / answering your final questions explicitly:

* The additional swaps you point out can be avoided without introducing other costs. So, as you suspected, they degrade performance compared to the final version in this answer.
* The version you suggest removes the unnecessary swaps, but introduces additional comparisons. So it will too perform worse than the final version in this answer.
* As I pointed out, the realitve performance of the original and your version will depend on the input at hand and the relative costs of swaps and compares. (Since usually compares are faster than swaps, I'd expect your version to be faster on average.)
> 13 votes

# Answer
# Some Context and History

FrankW's post answers most of the question, but I can add some references and give some context to it.

First of all, the algorithm is named after Dijkstra because of his 1976 programming book “A Discipline of Programming”, wherein chapter 14 deals with the so-called “Dutch National Flag Problem (DNFP)”:

*Rearrange an array of red, white and blue pebbles by swaps, such that their colors mimic the flag of the Netherlands.*

The DNFP was intended as a programming exercise and is maybe not interesting *per se*.
What is often needed, however, is **sorting** an array, and this is often done using **Quicksort** (see this question if you are interested in why is quicksort better than other sorting algorithms in practice).

## From flags to sorting

The crucial part in Quicksort is to *partition* an array around a pivot, i.e. *rearrange the array to have small elements to the left, elements equal to the pivot in the middle and large elements to the right.* — exactly like in the DNFP! Therefore, we can use the algorithms for the DNFP in the 3-way partitioning step for Quicksort.

> Is this excessive swapping needed for the algorithm?

As the algorithm from FrankW's answer nicely demonstrates, the extra swapping is not needed. Dijkstra gives an enhanced version of the algorithm in his book that avoids the extra swap, as well.

I suppose that Sedgewick used the version with the extra swap to keep the code concise — for educational reasons, so to say.

# What is “Performance”?

> Does it improve performance in some way? If it does improve performance, how?
>
> If it doesn't affect performance, please give a proper explanation or a proof as to why this it does not affect performance.
>
> Also, would the second method I mentioned affect performance in any way? please explain why.

First of all, performance depends on the input, especially the length of the array; but also on the number of elements equal to the pivot and so on. To answer you question, you will have to fix an input model.

Secondly, it is not clear what exactly we mean by “performance” ...
If we are interested in **total running time in seconds**, then the answer will depend on the machine/processor you use, the compiler, potentially the Java Virtual Machine, the OS, other processes ...
There will not be a definite answer to the above questions then, but you might run some experiments on your machine.

For *comparing* two alternative algorithms, it might be enough to compare a coarser measure, like the number of executed instructions: If one algorithm needs much more instructions, it will (usually) also be slower.

# Why Dijkstra's method is hardly used in practice

In the case of 3-way Quicksort, practical implementations (e.g. C++ standard library, Java 6 runtime library) use *“fat partitioning”*, a different partitioning scheme developed by Bentley and McIlroy (see their paper “Engineering a sort function”):

```
a = b = 0;
c = d = n-1;
for (;;) {
  while (b <= c && A[b] <= v) {
    if (A[b] == v) swap(A, a++, b);
    b++;
  }
  while (c >= b && x[c] >= v) {
    if (A[c] == v) swap(A, d--, c);
    c--;
  }
  if (b > c) break;
  swap(A,b++, c--);
}
s = min(a, b-a);
for(l = 0, h = b-s; s; s--) swap(A, l++, h++);
s = min(d-c, n-1-d);
for(l = b, h = n-s; s; s--) swap(A, l++, h++);

```

The invariant for the array is then

```
--------------------------
| = | <  |   ?   | > | = |
--------------------------

```

i.e. equal elements are put to the extreme ends and have to be swapped to the middle again at the end.

This method does in fact *more* swaps for many equal elements than your optimized Dijkstra partitioning. But it has almost no overhead for inputs without equal elements when compared to an optimized 2-way Quicksort; this is not the case for your algorithm: It would do roughly **three times** as many swaps on inputs without equal elements (see very similar computation here).

# Dual-Pivot Quicksort

A second way how the DNFP can help in Quicksort is when we use **two pivots** instead of one. Then, each partitioning step rearranges the array such that small elements are left, elements between the two pivots go to the middle and large ones to the right.

You may find it interesting that the Java 7 runtime library uses dual-pivot Quicksort with a partitioning method that is essentially your algorithm from above!
> 6 votes

# Answer
FrankW's answer above clearly answers my question, however I would like to add an answer from the stackoverflow copy of my question for anyone who bumps into this question. Answer from Yu Hao on StackOverflow

You are right, the extra swap operations are not necessary, this algorithm here is best for clarity, but not for performance. See the discussion of Quick Sort (3 Way Partition).

In Quicksort is optimal by Robert Sedgewich himself, he has a different approach that uses much less swap operation, but you can imagine it also needs more code, and is less clear than the algorithm in the demo.
> 0 votes

# Answer
I was in a confussion while doing merge and quick sort and i read this article here that clears my all doubts about quick sort

http://geeksprogrammings.blogspot.com/2014/02/algorithm-quick-sort-program.html
> 0 votes

---
Tags: algorithms, sorting, quicksort
---


# Question
Title: Why is $\sum_{j=1}^{n-1}[\Pi_{k=1}^{j}[(n-k)]]=2^n$?
In CLRS book, in the road cutting example there is a recursion formula

$$ 1+\sum\_{j=0}^{n-1}T(j) $$ and it can be proved that the sum is $$ 2^n $$

by simple induction. In 3-rd edition it is a formula 15.3 on a page 364.

As I can understand from the recursion-tree aproach, the recursion tree which can be built for the said problem is $$ 1-\>(n-1)-\>(n-2)|each.node-\>(n-3)|each.node-\>... $$

and so on, which can be summed as $$ \sum\_{j=1}^{n-1}\[\Pi\_{k=1}^{j}\[(n-k)\]\] $$

How can I come up with the suggestion of $2^n$ from this recursion tree (or why this tree is wrong and what can be the right approach to suggesting $2^n$ running time)?

# Answer
Minor nit: your first displayed expression should be $$ T(n) = \begin{cases} 1 & \text{if $n=0$,}\\ 1 + \sum\_{j=0}^{n-1}T(j) & \text{otherwise} \end{cases} $$ You can indeed solve this by looking at the recurrence tree, but you don't wind up with your sum of products expression (try it for $n=4$ to see that). For this problem there's an easier way, though:

**Hint**: What is $T(n+1)-T(n)$?

You can take a look at our reference question, on recurrence relations, as well.
> 4 votes

---
Tags: recurrence-relation
---


# Question
Title: What is complexity of checking whether a natural number is a perfect square?
As the title says, what is complexity of checking whether a natural number is a perfect square?

# Answer
For a given number $n$, binary searching for the square root $\sqrt n$ solves this problem in time $O(\log n)$.
> 2 votes

# Answer
There is a faster way to find (a good approximation of) the square root than the current answer (for 32-bit floating point numbers): a generalization of fast inverse square root (whose generalization you can read more about from this blog post) will give you the square root of a representable number. Normally, if you take the square root of a natural number you could lose some precision in floating point arithmetic of the result, but a perfect square will have its square root perfectly representable because the square root will also be an integer.
> 0 votes

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


title: Learning Quadratic Functions

text:
# Question
Title: Learning Quadratic Functions
I have seen in some ML tutorial that functions of the form $f(\vec x) = \vec x^T A \vec x$ ($\vec x \in \mathbb{R}^n$ and $A$ is an $n\times n$ real matrix) can be PAC learned.

Can anyone point me to a reference to this fact?

# Answer
One approach is to use linear regression.

The matrix $A$ has $n^2$ entries; treat each of those entries as an unknown, so you have $n^2$ unknowns. Now when $x$ is known, $f(x)$ is a linear function of those unknowns. If you have a set of equations $f(x\_i)=y\_i$ that are all known to be exactly correct, then you can solve for the unknowns by using linear algebra. If they are known to be approximately correct (e.g., $||f(x\_i)-y\_i||\_2$ is small), you can use least squares to find the solution for the unknowns that minimizes the sum of the squared errors (that minimizes $\sum\_i ||f(x\_i)-y\_i||\_2$). If a $1-\epsilon$ fraction of them are approximately correct, where $\epsilon \ll 1/n$, then you can pick a random subset of $n$ of them, guess that all of the ones in the subset are correct, use least squares to solve for the unknowns, and check whether that solution seems valid given the remaining equations, and repeat until you find a good solution.
> 2 votes

# Answer
Perhaps to complement D.W.'s answer: given an unknown matrix $A$, we are interested in finding a consistent algorithm. That is, given a list of $m$ vectors and their values $(\vec x\_1,v\_1),\dots,(\vec x\_m,v\_m)$, find some matrix $A^\*$ such that for every $\vec x\_j$ we have $\vec x\_j^TA^\* \vec x\_j = v\_j$ for all $j \in \[m\]$. Since $\vec x\_j$'s are given, we just need to solve the following linear system: find $(a\_{qr})\_{q,r \in \[n\]}$ such that
$$ \forall j \in \[m\]: \sum\_{q = 1}^n\sum\_{r = 1}^na\_{qr}x\_{j}(q)x\_{j}(r) = v\_j $$ (here $x\_j(q)$ is the $q$-th coordinate of $\vec x\_j$). Since we know that

1. There exists some solution (namely $A$ that we do not know)
2. This is a linear system with $\mathcal O(n^2)$ variables.

We can find a solution $A^\*$ to the above system in poly time. In particular, this implies that there is a consistent algorithm. Now, suppose that we limit ourselves to matrices that take integer values in $\[-M,M\]$; then there are $(2M)^{n^2}$ possible hypotheses. In other words, if our hypothesis class $\mathcal C$ is the set of all quadratic functions in the range $\[-M,M\]$, the log size of $\mathcal C$ is $\mathcal O(n^2\log M)$.

The existence of a consistent algorithm, along with the above bound on the log size of $\mathcal C$ implies that quadratic functions are $(\varepsilon, \delta)$-PAC learnable in time polynomial in $\frac 1\varepsilon,\log \frac1\delta, n^2,$ and $\log M$.

However, I am still looking for a reference to this (seems like a simple enough fact to be cited somewhere).
> 2 votes

---
Tags: reference-request, machine-learning
---


# Question
Title: How do I continue learning programming, beyond the basics?
DISCLAIMER: I understand that I might not be posting in the right part of StackExchange, or this question might have been asked before (I haven't found it). If this offends anybody, I apologize.

I'm 15 and a sophomore in High School. I have an interest in Computer Science in general. The thing is, I've learned a few languages here and there, but I just *don't know how to keep learning on a regular basis.* What I mean by this is that yeah, I can make a calculator with java, or some really basic scripts with python, but the fact of the matter is that I don't know what to do after that. Making a script that can count the words in a book seems so pointless.

What can I do to learn a programming language, practice it, and have an overall mastery of it? Anybody can learn how to do basic things like I've done, but what can I do so that at the end of some time, I can look back and say "yeah, I'm a real programmer now." I know that sounds cheesy, but help me out here.

# Answer
> 0 votes
If you're looking for some hands-on programming experience that also allows you freedom to do what you want, why not join an open source project? One such project is the Sage Math project

http://www.sagemath.org/development.html

It basically is an open-source project that develops a Python-like language for coding math. It has some cool features, especially in algebra and graphs, but also suffers from many bugs. Of course, there are many other open source projects you could find.

This would help you on many levels

1. Learn at your own pace
2. Work on anything that you like (provided that it is math related)
3. It will give you hands on experience at code development, committing, bug reporting and tracking. Basically anything and everything that you'll ever need to become a full-on programmer. Many people who work on such projects are top notch experts in their fields, so this could be a real opportunity.
4. You are contributing to society!

Alternatively, you could also take some online coding tasks (http://www.topcoder.com/) and even get paid for them. However, if your coding knowledge is not too great, this may not be the ideal place to start.

Good luck!

---
Tags: learning-theory
---


# Question
Title: Decrease space complexity, how will time complexity increase?
I have a problem whose lower bound of problem complexity is proven to be $O(n+m)$ (n \< m) and I also come up with an algorithm whose time complexity is $ O(n+m)$, space complexity is $ O(n)$. (All on deterministic turning machine)

If there exists an algorithm that uses O(1) space to solve the same probelm, what will be its lowest time complexity?

To ask in another way, if space complexity decrease from O(n) to O(1), what at least time complexity will increase from O(n+m)?

# Answer
> 1 votes
It depends on the problem. There's no general rule.

The running time could be as low as $O(n+m)$: for some problems, there exists an algorithm with running time $O(n+m)$ and $O(1)$ space. (Think about finding the maximum of an array with $n+m$ elements, for example.)

The best possible running time could also be as arbitrarily large. For instance, think of analyzing connectivity in graphs: given a graph and two vertices $s,t$, determine whether there's a path from $s$ to $t$. Let $n$ denote the number of vertices and $m$ the number of edges in the graph. There is a simple algorithm with running time $O(n+m)$ and space complexity $O(n)$, namely, depth-first search. However, there is no known algorithm whose running time is polynomial in $n$ and $m$ and that uses only $O(1)$ space.

See also https://cstheory.stackexchange.com/q/4556/5038 and https://cstheory.stackexchange.com/q/832/5038 for more technical details on this.

Terminology nitpick: problems have a complexity; algorithms have a running time. the complexity of a problem is the running time of the best algorithm for that problem.

---
Tags: complexity-theory
---


title: Adding concept drift to data sets

text:
# Question
Title: Adding concept drift to data sets
I'm about to work with concept drift problem in data streams.

I need to start with real data sets from UCI machine learning repository and add to them concept drift (in attributes domain).

Do you know tools that can help me with this? Maybe someone knows it is possible to use MOA\[1\] framework for this?

What is best way to approach this if I have to do it by myself?

\[1\] http://moa.cms.waikato.ac.nz/

# Answer
> 1 votes
It sounds like you are trying to generate a synthetic data set, by artificially adding fake drift.

This is a bad idea. Don't do this.

If you manage to find some algorithm that works well on your synthetic data set, then all you will know is that your algorithm works on a fake data set -- but you'll have no idea whether it is useful in practice.

Instead, I suggest that you try to find some real-world data sets that contain concept drift, and use them to work with. If you're not sure how to do that, you might not be ready to do research in this area yet: you might want to spend some time talking to your advisor/mentor, or spend a bunch of quality time in the library reading papers in the literature that talk about the concept drift problem.

---
Tags: machine-learning, data-mining
---


# Question
Title: Is it true that $FP^{NP[log\cdot n]} = FP^{NP}$ if $P = NP$?
Is it true that $FP^{NP\[log\cdot n\]} = FP^{NP}$ if $P = NP$?

If I understand the polynomial hierarchy correctly, then, if $P = NP$, all complexity classes collapse to one class. Therefore the above two classes should also be equal.

# Answer
> 5 votes
# The reverse

The reverse is true. If $FP^{NP\[log\]} = FP^{NP}$ then $P = NP$.

You can quickly find this in the Complexity Zoo; It was proven in M. Krentel. The complexity of optimization problems, Journal of Computer and System Sciences 36:490-509, 1988.

# The actual question

The other way around is easier. To quote the definition from Complexity Zoo:

> $FP^{NP\[log\]}$: $FP$ With Logarithmically Many Queries To $NP$

Therefore, if $P = NP$, $FP^{NP\[log\]} = FP^{P\[log\]}$. Logarithmically many queries to $P$ is certainly a subset of $NP$, so (if $P = NP$) $FP^{NP\[log\]} = FP^{NP}$.

---
Tags: complexity-theory, complexity-classes
---


title: Programming Languages Grammar Ambiguity

text:
# Question
Title: Programming Languages Grammar Ambiguity
I don't know if it is the right site to ask this. But we're studying about ambiguities of grammar. Including left most derivation and right most derivation. We are given the problem:

```
E -> E * E | E + E | N
N -> 0N | 1N |
Output: 0110 + 110 * 01111

```

My question is, is there a shortest way to attain that output? Because in my leftmost and rightmost derivation it took 7 lines.

# Answer
> 1 votes
As you said, the grammar is ambiguous.

There are two ways of producing the result $0110 + 110 \ast 01111$:
The one for $(0110 + 110) \ast 01111$ and the other for $(0110 + 110) \ast 01111$.
Try them both.

---

As for your question,

> Is there a shortest way to attain that output? Because in my leftmost and rightmost derivation it took 7 lines.

"Number of Lines" sounds quite vague.

---
Tags: formal-grammars, programming-languages, ambiguity
---


# Question
Title: Articulation vertex in complementary graph
I need to implement an algoritm, but I can't understand the theory behind it.

How can I prove that if v is an articulation vertex in a graph G , that it will not be an articulation vertex in G' complimentary graph ?

I know that an articulation vertex , is one which when removed disconects the G . And that the complementary graph , is one with two distinct vertices adjacent if and only if they are not adjacent in G.But I can't figure out how to connect this statements with my problem.

# Answer
> 2 votes
**Hint:** An equivalent characteristic of "an articulation vertex $v$" is as follows:

> $v$ is an articulation vertex in $G$ $\iff$ there exists two vertices $x,y$ such that $v$ is on all the paths between $x,y$.

So it suffices to check all the pairs $x,y$ in $G'$ to see whether there exists some path between them which *does not* pass $v$.

---

**More hints:**

Consider two cases:

1. In $G$, $v$ is on all the paths of $x,y$. Then is $e = (x,y) \in G'$?
2. In $G$, $v$ is not on all the paths of $x,y$. Where are $x$ and $y$ if $v$ is removed in $G$? Then,

2.1 What if $(x,y) \notin G$?
2.2 What if $(x,y) \in G$? Can you find a path $x \leadsto y$ in $G'$ which does not pass $v$?

---
Tags: graphs
---


title: Infix to prefix

text:
# Question
Title: Infix to prefix
According to this algorithm: http://en.wikipedia.org/wiki/Shunting-yard\_algorithm

when a left parenthesis is found, it is inserted into the stack, and when a right parenthesis is found, we pop all operands up to the left parenthesis. Neither parenthesis is included in the output.

But what if I want expressions such as "function(x) + 5" or "array\[x\] + 5"? How would the algorithm work when '(', ')', '\[', '\]' are seen as operands?

Can someone show me the prefix version of, say, "a\[x\] + 5"?

# Answer
The operations must be made explicit as functions first. An expression such as

```
function(x) + array[x] + 5

```

really is special syntax for something like this:

```
sum(sum(apply_function(function, x), array_element(array, x)), 5)

```

which can then be translated to postfix notation:

```
function x apply_function array x array_element sum 5 sum

```

and that is pretty much what it would look like in a language based on postfix notation, such as PostScript.
> 1 votes

---
Tags: algorithms, binary-trees
---


title: A proof that P != NP

text:
# Question
Title: A proof that P != NP
I came up with the following. Am I doing something wrong?

Suppose $P=NP$. Let $A$ be an NP hard problem. Let $A'$ be the polynomial reduction of $A$. By the assumtions, the Halting problem holts for $A$. Let $T'$ be the running time of $A'$. Clearly, $T' \in O(P(n))$, with $n$ as input size for $A'$ and $P(n)$ representing the class of polynomial functions of $n$. By that, the running time of $A'$ is bounded above and since it is a polynomial reduction of $A$, the running time of $A$ should also be bounded above. By that, there exists an algorithm, namely $X():=$return $True;$ which is a solution to the Halting problem for $A$. By that, the Halting problem does not hold for $A$, which is a contradiction. So the assumption that $P=NP$ can not hold and therefore $P \neq NP$.

# Answer
> Let $A$ be an NP hard problem

The halting problem, among others, is $NP$-hard. Did you mean to pick a $NP$-complete problem instead?

> Let $A'$ be the polynomial reduction of $A$.

What is "the polynomial reduction", where is it defined? Reduction to/from *what*? Do you mean that $A'$ is a polynomial algorithm that solves $A$? (Which would exist by virtue of your $P=NP$ assumption and $A$ being in $NP$.)

> the Halting problem holts for $A$

What does it mean for the Halting problem to holt (hold?) for $A$? The halting problem isn't parameterized on any particular program.

> the running time of $A$ should also be bounded above

$A$ does not have a running time. It is a problem, not an algorithm.

> There exists an algorithm \[...\] is a solution to the Halting problem for $A$

For any program $P$ there is an algorithm that computes whether or not $P$ halts. Namely, the algorithm that trivially returns one of true/false. The Halting Problem doesn't state that there can be no algorithm that computes whether a particular program halts, but rather that there is no algorithm that is correct for *all* programs.
> 6 votes

---
Tags: algorithms, halting-problem
---


# Question
Title: Reducing a non-RE language to its complement
Is there a language $L$ such that both $L$ and $L$'s complement are non turing recognizable languages, but there is a reduction between them? I couldn't find one...

# Answer
Such a undecidable language $L$ can not be in $RE$, since if there was a computable reduction from $L$ to $\overline{L}$, then $L$ would be in $R$.

Let $x'$ be the value to which $x$ reduces. $x' \in L$ if and only if $x\not \in L$. We could then decide $x\in L$ by enumerating $L$, and stopping to report that $x\in L$ as soon as we encounter $x$, and report that $x\not \in L$ when we encounter $x'$. That would make $L$ decidable, which is a contradiction. So there can be no reduction from a language in $RE$ to its complement.

By a similar argument, such a language can not be in $co-RE$ either.

There does exist an undecidable language $L$ that can be reduced to its complement. To find one, we must consider a language that is neither in $RE$ nor in $co-RE$. Let $L\in RE$ be an undecidable language. Then

$L'=\\{0w|w\in L\\} \cup \\{1w|w\in \overline{L}\\}$

is not recursive enumerable nor is its complement (see here).

But there clearly is a reduction from $L'$ to $\overline{L'}$.
> 5 votes

---
Tags: formal-languages, reductions, undecidability
---


title: Is it Regular Language?

text:
# Question
Title: Is it Regular Language?
According to Wikipedia, Regular Language is Recognized by Some DFAs, or expressed by Regular Expression .. and all finite Language are regular but, not all regular is finite ..

that's mean it may be infinite language is regular ?

my example is L = {a^n b^n+1, n \>0 } is it regular ? it generate infinite set of strings how to represent it as DFA or a regular expression (can represent this language using RegExp ?).. i can guarantee the exact number, how to automata to maintain the exact number of a's or b's

i tried some grammar, i do not get the regular grammar .. my grammar looks like

S -\> AB

A -\> aA | e

B -\> bbB | e

final question, how the language is regular and infinite in the same time ?

# Answer
Here's a derivation in your grammar, assuming that your 'e' denotes the empty string: $$ S\Rightarrow AB\Rightarrow B\Rightarrow bbB\Rightarrow bb $$ This is clearly not in $L=\\{a^nb^{n+1}\mid n\>0\\}$. There is, however, a non-regular grammar for your language: $$\begin{align} S&\rightarrow AB\\ A&\rightarrow aAb\mid ab &\text{generates $a^nb^n$}\\ B&\rightarrow b &\text{generates the $b$ on the right} \end{align}$$ There is no regular grammar that will generate $L$, since $L$ is not a regular language.

For your last question, "how can a language be regular and infinite?", you appear to be confused by your observation that any finite language is regular. This is true: logically we'd write this as "If a language is finite, then it is regular."

This does not, however, imply the converse: "If a language is regular, then it is finite." To see this, consider the true statement "If a number is a multiple of 6, then it is even". That's certainly true: 42 is a multiple of 6 and is also even. However, the converse, "If a number is even, then it is a multiple of 6" is certainly false sometimes, since 10 is even but not a multiple of 6. In logical notation, we have that the truth of $P\rightarrow Q$ does not guarantee that $Q\rightarrow P$.

The statement "If a language is finite, then it is regular" just says that the set consisting of finite languages are a subset of the set of regular languages, not that the two sets are the same. For example, the language $\\{a^n\mid n\ge 0\\}$ is regular (since that language is denoted by the regular expression $a^\*$ and also generated by the grammar $S\rightarrow aS\mid \epsilon$) but is obviously not finite.
> 2 votes

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


# Question
Title: Reduction from a further constrained problem
If I find an NP Hard problem that is equivalent to my problem with an additional constraint or bound, can I still prove that my problem is NP Hard?

Generally, this is probably not the case. For example, the NP Hard TSP is just a further constrained version of the shortest path problem.

Specifically, I have the problem:

> Given a universe $\mathcal{U}$ and a family $\mathcal{S}$ of subsets of $\mathcal{U}$, select $k$ sets from $\mathcal{S}$ such that the sum of the number of repeated times that each element is covered is maximized. Number of repeats are defined as one less than the number of instances.

If the number of repeated times for each element has an upper bound at 1, this is equivalent the densest k-subgraph problem (edges are elements and nodes are sets),

> Given a graph $G$ and an integer $k$, find a subgraph of $G$ on $k$ nodes with maximum number of edges.

Since the densest k-subgraph problem is strongly NP Hard, can I prove that my problem is also NP Hard?

# Answer
> 2 votes
Hint: An instance of densest $k$-subgraph can be viewed as an instance of your problem, in which sets are vertices and elements are edges.

More generally, to prove that a problem P is NP-hard given that a (seemingly) related problem Q is NP-hard, you need to come up with a polytime reduction from Q to P. If Q is strongly related to P, such a reduction could be easy to find.

---
Tags: graphs, reductions, np-hard, set-cover
---


# Question
Title: what is the advantage of using threaded trees?
Since a binary tree with $N$ nodes has $N+1$ NULL pointers (across leaves), half the space allocated in a binary search tree for pointer information is wasted. Suppose that if a node has a NULL left child, we make its left child point to its in-order predecessor, and if a node has a NULL right child, we make its right child point to its in-order successor. This is known as a *threaded tree* and the extra pointers are called *threads*. In what way this implementation helpful? Can any one provide useful information.

# Answer
> 1 votes
Threaded trees make in-order tree traversal a little faster, because you have guaranteed O(1) time to access the next node. This is opposed to a regular binary tree where it would take O(lg n) time, because you have to "climb" up the tree and then back down.

The trade off is that you're opting to determine what the next in-order node is when you insert into the tree, rather than when you're doing the traversal.

# Answer
> 1 votes
Threaded trees make it possible to perform inorder-traversal without the use of stack or recursion. The threads make it possible to back-up to higher levels. Thre is a catch: we should be able to distinguish threads from ordinary links, and the obvious way to do that is to use a bit for each link, to mark the threads. However, there are (very inefficient) techniques to check threads vs. edges in unmarked trees.

---
Tags: data-structures, trees
---


title: Lambda Calculus Notation

text:
# Question
Title: Lambda Calculus Notation
I'm reading through the paper `Transactors: A Programming Model for Maintaining
Globally Consistent Distributed State in Unreliable
Environments` by John Field and Carlos Varela.

I have basic knowledge about the lambda calculus (typed lambda calculus to be more precise) thanks to a class I took at my university.

However, I'm stuck finding out what the rule shown below actually means. I have looked through the `Types and Programming Languages` book by Benjamin Pierce but I can't seem to find an explanation.

Could somebody help me understand what rule `pur7` means?

# Answer
It probably depends on what $\mathcal{F}$ is -- the text tells you.
Each $f\in\mathcal{F}$ is a build-in/primitive function (such as $+$) and \[pur7\] gives the result of applying it to some arguments. $\[\\!\[ f\]\\!\]$ gives the semantic interpretation of the function, and applying that to the arguments $v\_1,\ldots,v\_n$ gives the result of the function.
> 3 votes

---
Tags: lambda-calculus, types-and-programming-languages
---


# Question
Title: Algorithm to find shortest path between two nodes
I want an algorithm similar to Dijkstra or Bellman-Ford for finding the shortest path between two nodes in a directed graph, but with an additional constraint.

The additional constraint is that there are $N$ sets of special edges with weight $0$ such that a path is not considered valid if it traverses one edge in a set but not the remaining edges in that set.

Note that these $N$ sets of edges are disjoint such that no edge belongs to more than one of the $N$ sets. The number of edges in each set is around 3 to 6. And there are a large number of these sets. About $50\\%$ of edges belong to a set, the rest don't belong to a set and can be traversed normally.

Does such an algorithm exist? Can such an algorithm exist that is better than brute force?

# Answer
> 4 votes
It is $NP$-complete, and thus it is unlikely that a polynomial algorithm ("better than brute force") exists. Proof is by reduction from Hamiltonian $s-t$-Path:

Every edge in the input graph $G=(V,E)$ is given weight $1$. The graph is then duplicated, and special (weight 0) edges are added between corresponding vertices in the two graphs. We thus get two copies of the original graph, and the copies are linked by $|V|$ special edges between the two copies of the same vertex. Call these new edges the 'copy' edges.

$|V|$ vertices are added to the graph and connect in a chain with $|V|-1$ new special (weight) 0 edges. Another special (weight 0) edge is added to connect the end vertex to $s$. Call these new edges the 'chain' edges.

Partition the $2|V|$ new edges into $|V|$ edge sets that each consist of one copy edge and one chain edge.

We now try to find a shortest path between the start of the chain and vertex $t$ that satisfies your requirement of traversing either all or none of the edges from each edge set. Such a path must start by traversing the full chain, so it must contain all chain edges, so it must contain all copy edges, so it must visit every vertex of the original graph; therefore, omitting all special edges from it will produce a Hamiltonian path from $s$ to $t$, if one exists.

Deciding whether a Hamiltonian path between arbitrary edges $s$ and $t$ exists is known to be $NP$-complete, so your problem is $NP$-hard: if you can find a polynomial algorithm for it (such as Dijkstra's), you will have proved $P=NP$.

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: What happens to multi-qubit quantum state after one of qubits is measured?
If we have a quantum state consisting of (let's say) 3 entangled qubits and we read the value of one of them, what happens to the probabilities of the remaining possible states?

For example, if we have three entangled qubits and have an amplitude for every state from $|000\rangle$ to $|111\rangle$ and we measure the second (middle) qubit to be 1, the remaining states are $|010\rangle, |011\rangle, |110\rangle, |111\rangle$. If we know the amplitudes for all possible 9 states before the measurment, how do we get the amplitudes of the remaining states after measurment?

# Answer
> 8 votes
The amplitudes are scaled so that their norm is 1. In your case, if the original amplitudes are $\alpha\_{000},\ldots,\alpha\_{111}$, then after measuring the second bit to be 1, which happens with probability $p = \alpha\_{010}^2 + \alpha\_{011}^2 + \alpha\_{110}^2 + \alpha\_{111}^2$, the quantum state is $$ \frac{\alpha\_{010} \left|010\right\rangle + \alpha\_{011} \left|011\right\rangle + \alpha\_{110} \left|110\right\rangle + \alpha\_{111} \left|111\right\rangle}{\sqrt{\alpha\_{010}^2 + \alpha\_{011}^2 + \alpha\_{110}^2 + \alpha\_{111}^2}}. $$

---
Tags: quantum-computing
---


title: How does "do in parallel" work

text:
# Question
Title: How does "do in parallel" work
currently i'm preparing for an exam in a high performance computing course. In this course we discuss several common parallel algorithm patterns called "dwarfs". The first dwarfs we had was the "dense linear algebra", so basically matrix multiplication. In one of the first slides there is a example for a basic matrix multiplication:

```
MatrixMult PRAM(A:Matrix[n], B:Matrix[n], C:Matrix[n]) {
for i from 1 to n do in parallel
    for k from 1 to n do in parallel
        for j from 1 to n do
            C[i,k] = C[i,k] + A[i,j]∗B[j,k]
}

```

Nothing really fancy, just the basic matrix multiplication. But below this piece of code the slide states:

> • synchronized execution of the for-j-loop;
>
> → in the first step:
>
> • all processors $P\_{i,k}$ simultaneously access A\[i,1\]
>
> • all processors $P\_{i,k}$ simultaneously access B\[1,k\]

I don't understand why all processors access these elements at the same time. I thought every processor has a different value for i and k, so every processor should access a different element. For example, n=3:

1. Time step (execute first for loop in parallel on all P):
    * P1 -\> i = 1
    * P2 -\> i = 2
    * P3 -\> i = 3
2. Time step (execute second for loop in parallel on all P):
    * P1 -\> k = 1
    * P2 -\> k = 2
    * P3 -\> k = 3
3. Time step (execute third for loop sequential on all P):
    * P1 -\> j = 1, i=1, k=1 ==\> A\[1,1\] B\[1,1\]
    * P2 -\> j = 1, i=2, k=2 ==\> A\[2,1\] B\[1,2\]
    * P3 -\> j = 1, i=3, k=3 ==\> A\[3,1\] B\[1,3\]
4. Time step:
    * P1 -\> j = 2
    * P2 -\> j = 2
    * P3 -\> j = 3
5. etc..

So in the third time step every processor would access another element. So i'm not quite sure if i understand the "do in parallel" statement correct. I thought that every statement in this loop would be executed on every processor but with different index as Joseph JáJá defines the "pardo statement" (i think it's the same like "do in parallel") as follows:

> for l $\leq$ i $\leq$ u **pardo** statement
>
> The statement (which can be a sequence of statements) following the pardo depends on the index i. The statement corresponding to all the values of i between l and u are executed concurrently (from "An Introduction to parallel algorithms", Jospeh JáJá page 27)

So the question is, why do all processors access the same element and how does the "do in parallel" statement work? I'm not sure if i understood this statement.

# Answer
Two consequent parallel loops maybe joined like "product", so this code can be effectively parallelized up to $n^2$ (9 in your example) processors. Each such processor can be indexed by $i,k$ pair.

Now,

> all processors $P\_{i,k}$ access simultaneously $A\[i,1\]$

means that all processors which have the first index equal to $i$ and second index equal to anything (to some $k$ but it does not restrict the cell), will simultaneously access $A\[i,1\]$. In your example, you parallelize only by $i$ (first for loop), so you have only one processor per each such cell. If you parallelize completely (by pairs $(i,k)$), you will have $n$ processors per each such cell.
> 0 votes

---
Tags: parallel-computing, matrices
---


# Question
Title: Efficient algorithm to fulfil a set of coordinate constraints
I have a set of labelled points and a set of distance constraints between pairs of points, consisting of a lower and upper distance bound. There is definitely an arrangement of the points in 3D space that fulfils all distance constraints.

I wish to generate arrangements of the points where all constraints are fulfilled. Any approach is allowed as long as each arrangement is independently generated from the others.

What algorithm is most suitable? Mainly in terms of efficiency.

As an extension, how would I incorporate constraints on the angle defined by three points? And on the dihedral angle defined by four points (the dihedral angle between points ABCD is the angle between the plane defined by ABC and the plane defined by BCD)?

# Answer
> 2 votes
The simplest approach (in terms of programming effort) might be to try using an existing graph layout tool. Those solve a related problem: given a graph with distances on the edges, try to find the best layout to draw the graph on the plane. You can treat your problem as an instance of the graph layout problem: we have one vertex per point, and for each pair of points $v,w$ with distance bounds $\[\ell,u\]$, we create an edge $v \to w$ with length $(\ell+u)/2$. However, this does have some limitations: typical graph layout algorithms try to get the distances between vertices correct, but also try to avoid edges that cross each other; whereas in your case you don't care about crossings. So, your problem might be easier.

Another possibility is to apply the ideas used for graph layout to your problem. There are several algorithmic techniques for graph layout. For instance, you could use a spring-based model, where you have a spring between each pair of vertices that have a distance bound, and the spring tries to keep those pair of vertices a suitable distance apart.

A third approach is to use black-box mathematical optimization. Introduce an objective function $\Phi$ which, given a set of locations for the points, calculates a penalty value (how "badly" the arrangement violates your constraints), and then try to find an arrangement that minimizes $\Phi$.

For instance, suppose for each pair $v,w$ of points, you have a lower bound $\ell\_{v,w}$ and an upper bound $u\_{v,w}$. You could define

$$\Phi(x\_1,\dots,x\_n) = \sum\_{i,j} \frac{\[||x\_i - x\_j||\_2 - (u\_{i,j} + \ell\_{i,j})/2\]^2}{(u\_{i,j} - \ell\_{i,j})^2},$$

and then use some optimization technique to find an arrangement $x\_1,\dots,x\_n$ that minimizes $\Phi(x\_1,\dots,x\_n)$. For instance, you could try using hillclimbing, gradient descent, or other convex optimization methods. This approach might be sensitive to the initial values for $x\_1,\dots,x\_n$, so you might want to repeat it multiple times with different random choices for the initial value, and take the best result.

Finally, you could try using simulated annealing.

---

The latter two approaches can be easily adjusted to incorporate angle constraints, simply by modifying the objective function appropriately to add a term that penalizes angles that differ from the desired value.

---
Tags: constraint-programming, euclidean-distance
---


# Question
Title: How to interprocess communication and scheduling algorithms interact?
I was listening back to a lecture I had, hinting on what we should revise for our upcoming exam. Since then I've covered all the parts, but having difficult in decrypting the following

> You might want to look at the interaction between scheduling algorithms and interprocess communication.

I understand both interprocess communication and scheduling algorithms but don't have an opinion/nor can find one on the link between the two. If anyone could inform me I'd really appreciate it.

# Answer
Such interaction arises when a high-priority task needs to communicate in some way with a low-priority task. Scheduling algorithms may need to take into account such communication. For example, see http://en.wikipedia.org/wiki/Priority\_inversion .
> 2 votes

---
Tags: operating-systems
---


title: Understanding Multilevel Caches

text:
# Question
Title: Understanding Multilevel Caches
I'm reading multi-level cache and came across a question through which i got confused. I've read that

> * Between processor and Cache Word/ Byte is transfered
> * Between Cache and Main memory Block(Block of words) is transfered.
> * If there is a miss in lower level cache and hit in higher level cache, first Block of words is transfered from higher level cache to lower level cache and then particular words is transferred to the ptocessor from lower level cache.

In case of multi-level caches cache at lower level generally has lower size as compared to cache at higher level. Hence Block size of lower level cache is generally smaller than block size of higher higher cache.

So, `How actually Block of words is transferred between caches.`

For instance suppose there two caches $L\_1$ and $L\_2$ with block size 4 words and 16 words respectively, connected with a databus having capacity to transfer 4 words at a time. Now Suppose there is a miss in $L\_1$ cache and a hit in $L\_2$ cache. Then Do we transfer 16 words or only 4 words from $L\_2 \rightarrow L\_1$

# Answer
It depends. What is the level of associativity of L1? If it's a direct mapped cache, then naturally, you will have to transfer 4 words of data from L2 to L1. If it's a 2-way set associative, then 8 words. This makes the interface between L1 and L2 as simple as possible given their configurations.

The idea is to make the hit time of L1 and miss rate of L2 as low as possible.
> 1 votes

# Answer
Block sizes (aka Cache line lenghts) can be different on different levels of caches. L1 caches should be optimised for the type of access the CPU does while L3 caches should be optimised for the burst lenght and data width of the attached DRAM memory.

It is possible to fill/spill only one block of the L1 with a larger block sized L2 (in your example 4 words). On write back, either the whole L2 block is marked as modified, or use sub-blocking (effectively reducing block size without raising associativity).

One advantage with using the same size is probably with exclusive caches (AMD did that many times) : As soon as a block is in L1, copied from L2, the L2 block can be made available for new data.

**Edit**

Many examples there : http://www.7-cpu.com/ Using different block sizes across different cache levels seems very rare : Several recent x86 use 64Bytes, ARMs 32Bytes, PowerPCs 128Bytes, but they keep the same size on all levels. Note also the bus width : Internal busses can be extremely large, able to transfer 16 or 32 bytes in one cycle.
> 1 votes

---
Tags: computer-architecture, cpu-cache
---


# Question
Title: Three-address code versus JSON, XML, etc
I'm working on a compiler. The textbooks I have say to output a 3-address intermediate code. This can be translated into the target language of choice.

I don't have a problem with the bulk of the source being translated to 3-addr code. But for the data-rich symbol table, this is awkward.

Is the exclusive use of 3-addr code old, obsolete advice? My compiler is multi-pass compiler. I'm working pretty hard to build a symbol table in my first pass, and I'm pretty much having to reconstruct it in 3-address code for the next pass. This seems like make-work to me when I could create from my symbol table XML or JSON. I could write that to the intermediate file instead.

How should I represent my symbol table in the intermediate code?

# Answer
XML and JSON are formats for representing data. The actual kind of data depends upon how you use them. For instance, they could be used to represent 3-address intermediate code or an abstract syntax tree, or even a symbol table.

3-address intermediate code is best generated only at the very end, as input to the code generator. For all other passes, keep as much information around as possible. This could include a decorated abstract syntax tree (decorated with types and other information) and a symbol table.

In fact, I'd only use the 3-address format if you are generating assembly. For a higher level target language, use a higher-level intermediate format.
> 5 votes

---
Tags: compilers
---


title: Proof problem is NP

text:
# Question
Title: Proof problem is NP
Hi need help to proof:

For each A,B problems , if A ≤p B , and B ∈ NP then A ∈ NP

Thanks.

# Answer
There are two equivalent definitions of $\text{NP}$.

The one is verifier-based:

> $\text{NP}$ is the set of decision problems whose solutions can be *verified* in polynomial time.

The other one is machine-based:

> $\text{NP}$ is the set of decision problems which can be *solved* in polynomial time by some *non-deterministic* (Turing Machine) algorithm.

**Hint:** Try both definitions to see which one is more suitable to your problem.

---

Maybe you can first solve the easier problem to warm up:

> If $A \le\_{p} B$ and $B \in P$, then $A \in P$.
> 2 votes

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


# Question
Title: Proof that Hamiltonian cycle/circuit with a specified edge is NP-complete
I'm a little stuck on this question, any help would be appreciated!

Given that the Hamiltonian Path (HP) and the Hamiltonian Circuit/Cycles (HC) problems are known to be NP-complete, show that HCE is NP-complete.

HCE: Given an undirected graph G and an edge e of G, does G have a Hamiltonian circuit/cycle that uses e?

I've tried to approach this by showing that HC $\leq$ HCE, but I'm wondering if my approach is too convoluted.

**EDIT:**

I think I have a solution. Consider a graph $G=(V,E)$ where $V$ is the set of vertices in $G$, and $E$ is the set of edges in $G$. Let $f(G)=G'=(V',E')$ where

\begin{alignat\*}{1} V'= & V\cup\\{v\_{\alpha},v\_{\beta},v\_{\gamma}\\},v\_{\alpha},v\_{\beta},v\_{\gamma}\notin V\\ E'= & E\cup\\{(v\_{\alpha},v\_{\beta}),(v\_{\beta},v\_{\gamma})\\}\cup\\{\bigcup\_{i\in\\{\alpha,\gamma\\},v\in V}(v,v\_{i})\\} \end{alignat\*}

Let the edge $e=(v\_{\alpha},v\_{\beta})$.

$G'$is the graph $G$ with three additional vertices. $v\_{\alpha}$ and $v\_{\gamma}$ are connected to all the vertices in $G$ and $v\_{\beta}$. $v\_{\beta}$ has a degree of 2, and is only connected to $v\_{\alpha}$and $v\_{\gamma}$. $f$ can be computed in p-time.

Consider some $G$ that has a HP along vertices $v\_{1},v\_{2},...,v\_{n}$. Then $G'$ will also have a path $v\_{1},v\_{2},...,v\_{n}$ with each vertex only appearing once in the path. In order to turn this path into a HC, the three additional vertices will have to be included. In order to do so, the path has to be extended in either $v\_{n},v\_{\alpha},v\_{\beta},v\_{\gamma},v\_{1}$ or $v\_{n},v\_{\gamma},v\_{\beta},v\_{\alpha},v\_{1}$. $G'$ thus have a HC that will always include the edge $e$.

$\therefore$ G $\in$ HP $\implies$$f(G)=G'\in$ HCE

Consider some $G'$ with a HCE along some path $v\_{1},v\_{2},...,v\_{n},v\_{\alpha},v\_{\beta},v\_{\gamma},v\_{1}$. Since $G$ has vertices $V=V'\backslash{v\_{\alpha},v\_{\beta},v\_{\gamma}}$, $G$ has a HP along vertices $v\_{1},v\_{2},...,v\_{n}$.

$\therefore$ $G'\in$ HCE $\implies G\in$ HP

And thus $G\in$ HP iff $f(G)=G'\in$ HCE. Since $f$ can run in p-time, HP $\leq$ HCE.

$\therefore$ HCE is NP-complete.

# Answer
> 1 votes
I think I have a solution. Consider a graph $G=(V,E)$ where $V$ is the set of vertices in $G$, and $E$ is the set of edges in $G$. Let $f(G)=G'=(V',E')$ where

\begin{alignat\*}{1} V'= & V\cup\\{v\_{\alpha},v\_{\beta},v\_{\gamma}\\},v\_{\alpha},v\_{\beta},v\_{\gamma}\notin V\\ E'= & E\cup\\{(v\_{\alpha},v\_{\beta}),(v\_{\beta},v\_{\gamma})\\}\cup\\{\bigcup\_{i\in\\{\alpha,\gamma\\},v\in V}(v,v\_{i})\\} \end{alignat\*}

Let the edge $e=(v\_{\alpha},v\_{\beta})$.

$G'$is the graph $G$ with three additional vertices. $v\_{\alpha}$ and $v\_{\gamma}$ are connected to all the vertices in $G$ and $v\_{\beta}$. $v\_{\beta}$ has a degree of 2, and is only connected to $v\_{\alpha}$and $v\_{\gamma}$. $f$ can be computed in p-time.

Consider some $G$ that has a HP along vertices $v\_{1},v\_{2},...,v\_{n}$. Then $G'$ will also have a path $v\_{1},v\_{2},...,v\_{n}$ with each vertex only appearing once in the path. In order to turn this path into a HC, the three additional vertices will have to be included. In order to do so, the path has to be extended in either $v\_{n},v\_{\alpha},v\_{\beta},v\_{\gamma},v\_{1}$ or $v\_{n},v\_{\gamma},v\_{\beta},v\_{\alpha},v\_{1}$. $G'$ thus have a HC that will always include the edge $e$.

$\therefore$ G $\in$ HP $\implies$$f(G)=G'\in$ HCE

Consider some $G'$ with a HCE along some path $v\_{1},v\_{2},...,v\_{n},v\_{\alpha},v\_{\beta},v\_{\gamma},v\_{1}$. Since $G$ has vertices $V=V'\backslash{v\_{\alpha},v\_{\beta},v\_{\gamma}}$, $G$ has a HP along vertices $v\_{1},v\_{2},...,v\_{n}$.

$\therefore$ $G'\in$ HCE $\implies G\in$ HP

And thus $G\in$ HP iff $f(G)=G'\in$ HCE. Since $f$ can run in p-time, HP $\leq$ HCE.

$\therefore$ HCE is NP-complete.

# Answer
> 1 votes
**Given**: a graph $G$, an edge $e$, and a length $k$.

**Optimization problem output**: a cycle of length $k$, containing $e$ (or none, if there is none).

**Decision problem output**: "yes" if such a cycle exists, "no" otherwise.

Now, it is obviously in NP, as you can simply check any answer to the optimization problem; see if it is a cycle, see if the cycle contains $e$, and check that the length of the cycle is $k$.

There are two easy ways to prove it is NP-hard. Imagine you had a magic algorithm, ${\rm M{\small AGIC}}(G,e,k)$, that can answer this for you.

**Method 1 hint:** In the k-SAT to DHC (directed Hamiltonian cycle) reduction, aren't there some edges that *must* occur? (and don't these carry over to UHC (undirected Hamiltonian cycle)?)

More hints (mouseover):

> The reduction from k-SAT to DHC (directed Hamiltonian cycle) involved a root node, and a sink node. The sink node has an edge to the root node; and it is the only incoming edge to the root node; hence, the sink-root edge *must* be used in the DHC.
> Furthermore, in the reduction from DHC to UHC, each node gets split into 3 nodes, and the middle one is connected to the two outer ones with a single edge. Well, as a general rule, any degree-2 nodes make it easy to solve this problem (because the cycle *must* pass through it).

**Method 2 hint:** What happens if you pick a node. The Hamiltonian Cycle *must pass through one* of its edges. How many edges can a node have?

More hints (mouseover):

> Maybe you can solve a regular UHC with some calls to ${\rm M{\small AGIC}}(G,e,k)$.

# Answer
> 1 votes
This nice answer to CS theory post, Complexity of finding 2 vertex-disjoint (|V|/2)-cycles in cubic graphs?, provides an answer to your question (even when input graphs restricted to cubic graphs).

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


title: Is this language regular

text:
# Question
Title: Is this language regular
Let L is a regular language then is

L' = {x$\_2$x$\_1$| x$\_1$x$\_2$ ∈ L}

regular?

Thus x$\_1$x$\_2$ is essentially concatenation of two strings, but can reverse concatenation of same two strings yield regular language?

# Answer
The answer is yes. Suppose $A=(Q,q\_0,F,\delta)$ is a deterministic finite automaton (with set of states $Q$, initial state $q\_0$, set of final states $F$, and transition function $\delta$) recognizing the original language $L$. Then you can construct a nondeterministic automaton for $L'$ as follows:

For each state $q$ of $A$ create a separate copy of $A$, add $\epsilon$-transitions from its accepting states to the initial state, and then make $q$ the initial and (unique) accepting state. This gives you an NFA $A\_q=(Q,q,\\{q\\},T)$, with transition relation $T=\\{r,a,\delta(r,a)|r\in Q,a\in\Sigma\\}\cup\\{(r,\epsilon,q\_0)|r\in F\\}$. This NFA accepts a word $w$ if and only if there is a decomposition $w=uv$ such that $\delta(q,u)\in F$ and $\delta(q\_0,v)=q$, which implies $vu\in L$.

Let $A'$ be the union of all the $A\_q$. Then for any $uv\in L$, $vu$ is accepted by $A\_q$ for $q=\delta(q\_0,u)$, and therefore by $A$.
> 1 votes

# Answer
The language $L'$ is regular indeed.

Let $M$ be a DFA for $L$.

In order to prove it, build an NFA which "guesses" the state of the automaton $M$ after reading $x\_1$.

In order to do so, create $|Q|$ copies of $M$ (for each state $q\in Q$, create a copy $M\_q$), and a new initial state $q\_0'$ with a $\epsilon$-transition to each state $q$ inside the sub-automaton $M\_q$.

Next, we need that after reading $x\_2$, the automaton will be able to read $x\_1$, so add epsilon moved from each state $f\in F$ in $M\_q$ to $M\_q(q\_0)$ (the copy of the initial state of $M$), and make $q$ the only accepting state of $M\_q$.

(well, formally, in order to prevent accepting the empty word, if it wasn't a part of $L$, you'll need to create additional state $q'$ in $M\_q$ so that $q'$ will not be an accepting state, and the initial transition from $q\_0$ would go into $q'$).
> 1 votes

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


# Question
Title: Literature on network-flow (optimization) approximation algorithms
I've been searching on literature on approximation algorithms in the context of network-flow problems (optimization) to finish my bachelor degree.

However, I have been looking in several well-known algorithm books but, I haven't yet found something. Most books don't go beyond Ford-Fulkerson and/or Edmond-Karp in respect to network-flow problems, and the sections explaining approximation algorithms discuss some algorithms not relating to network-flow optimization.

Could someone point me towards appropriate literature? I prefer books instead of papers.

# Answer
In his FOCS2013 (Best Paper award) work, Aleksander Mądry gives a $\widetilde O(m^{\frac{10}{7}})$-time for exact max-flow and gives a nice survey on the existing techniques (including near-linear time for $(1+\epsilon)$-approximation in undirected graphs).
> 4 votes

# Answer
There's lots of literature in the computer vision community, as network flow has been used for many purposes. I know I've read survey papers from computer vision folks that compare a number of different algorithms for network flow to figure out which ones work best for computer vision applications.

For one example application, you could look at "seam carving": https://dl.acm.org/citation.cfm?doid=1435417.1435437
> 1 votes

---
Tags: reference-request, optimization, network-flow
---


# Question
Title: Getting minimum DFA for regular expression (11)*+(111)*
(sorry beforehand I know putting scanned diagrams may seem not-so-professional but this problem is sticking for long and its interesting too)

The language corresponding to given regex seems to accepts all strings of 1's with length in multiple of 2 or 3 (i.e.4,6,8,9,10,12,...)

I prepared following NFA first:

Figure 1

Then I followed steps given here to prepare DFA. First I prepared below table to get equivalent DFA steps:

Figure 2

Then I prepared below DFA, which seems to be quite correct.

Figure 3

Next to get equivalent states I followed table filling algorithm as explained \[here\] (http://books.google.co.in/books?id=tzttuN4gsVgC&lpg=PP1&pg=PA144#v=onepage&q&f=false) and formed below:

(cross between every intersecting column and row indicates two intersecting states are distinguishable / not equivalent)

Figure 4

But I dont get from above table how can I get below minimized DFA as given in the book solution:

Figure 5

So in the solution of the textbook, their is one less state (total 6) than my dfa in figure 3 (which has 7 states). I should be able to derive the same (equivalent 6-state dfa) from above triangular table.

# Answer
> 4 votes
The problem is that you did not make state $A$ accepting during $\epsilon$ transition elimination. Since it has $\epsilon$ transitions to accepting states, you should have done so. As a result, the automaton you obtain doesn't accept the empty word as it should. If you fix this, minimization then merges $A$ with $B,D$.

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


# Question
Title: Finding the $k$th largest element in an evolving query data structure
Basically, the problem I am solving is this. Initially, the array $A$ is empty. Then I am given data to fill the array and at any time I have to make a query to print the $|A|/3$-th largest element inserted so far.

I was solving the problem with segment trees, but I am not able to make a little modification to the query function of the segment tree. The query function that I wrote returns the largest element between indices $a\_{\text{begin}}$ and $a\_{\text{end}}$:

```
int query(int Nodenumber,int t_begin,int t_end,int a_begin,int a_end)
{
    if (t_begin>=a_begin && t_end<=a_end)
        return Tree[Nodenumber];
    else
    {
        int mid=((t_begin+t_end)/2);
        int res = -1;

        if (mid>=a_begin && t_begin<=a_end)
            res = max(res,query(2*Nodenumber,t_begin,mid,a_begin,a_end));

        if (t_end>=a_begin && mid+1<=a_end)
            res = max(res,query(2*Nodenumber+1,mid+1,t_end,a_begin,a_end));

        return res;
    }
}

```

Note to make a query, I call the query function as `query(1,0,N-1,QA,QB)`.

But I want to return the $|A|/3$-th largest element between indices $a\_{\text{begin}}$ and $a\_{\text{end}}$. So how should I modify the function to do this?

So updating, queries, updating, queries, updating, queries and so on are done randomly and several (upto $10^5$) times.

So, for solving the problem, did I pick the right data structure? I thought of using heaps, but that will be too slow, as I would have to pop $|A|/3$ elements from the top and reinsert them for every query.

# Answer
> 5 votes
Have a look at the Wikipedia page for segment trees:

> It is, in principle, a static structure; that is, its content cannot be modified once the structure is built.

So it does not seem to be a good data structure for your scenario at all.

Note that the kind of query you want to perform is called selection (unimaginative, I know). Check the linked article for loads of algorithms. One simple way to solve your problem is this:

* Store elements in a *sorted list*. That means, updates (that is insertions) take linear time.
* For the queries, run a selection algorithm on the specified interval.

This approach can be improved by extending the list to a skip list.

Another approach is using binary search trees. If you use a self-balancing variant, that makes updates possible in $O(\log n)$ time. The queries you want can be implemented by storing in every node how many descendants it has, so we can find the $k$-th largest element in $O(\log n)$ time.

# Answer
> 1 votes
You can use a segment tree to perform dynamic selection in $O(\log S)$ per oper; where $S$ is the size of the universe. To do this, you need to maintain the total number of elements in the segment represented by a node.

In fact, a binary indexed tree can also be used. Or you could also use a balanced binary search tree as Raphael suggested.

# Answer
> 1 votes
It is worth to mention that the problem is solvable with two heaps. You have to maintain a max heap for the first ~2\[A\]/3 element and a min heap for the last ~\[A\]/3 element. Inserting is O(log\[A\]), query is O(1).

---
Tags: algorithms, data-structures
---