# Question
Title: Finding preferences for G-S algorithm (Algorithm Design Chapter 1 exercise 7)
I'm working on Algorithm Design (Kleinberg-Tardos) Chapter 1 exercise 7:

> Some of your friends are working for CluNet, a builder of large communication networks, and they are looking at algorithms for switching in a particular type of input/output crossbar. Here is the setup. There are n input wires and n output wires, each directed from a source to a terminus. Each input wire meets each output wire in exactly one distinct point, at a special piece of hardware called a junction box. Points on the wire are naturally ordered in the direction from source to terminus; for two distinct points x and y on the same wire, we say that x is upstream from y if x is closer to the source than y, and otherwise we say x is downstream from y. The order in which one input wire meets the output wires is not necessarily the same as the order in which another input wire meets the output wires. (And similarly for the orders in which output wires meet input wires.) Figure 1.8 gives an example of such a collection of input and output wires. Now, here’s the switching component of this situation. Each input wire is carrying a distinct data stream, and this data stream must be switched onto one of the output wires. If the stream of Input i is switched onto Output j, at junction box B, then this stream passes through all junction boxes upstream from B on Input i, then through B, then through all junction boxes downstream from B on Output j. It does not matter which input data stream gets switched onto which output wire, but each input data stream must be switched onto a different output wire. Furthermore—and this is the tricky constraint—no two data streams can pass through the same junction box following the switching operation. Finally, here’s the problem. Show that for any specified pattern in which the input wires and output wires meet each other (each pair meeting exactly once), a valid switching of the data streams can always be found—one in which each input data stream is switched onto a different output, and no two of the resulting streams pass through the same junction box. Additionally, give an algorithm to find such a valid switching.

This is the algorithm I've came up with so far:

1. Input wires prefer output wires in the order the signal meets each output wire from source to terminus.
2. Output wires prefer the source input wires of downstream junctions to source input wires of upstream junctions.
3. Let M be the matchings after applying the G-S algorithm using the input wires, output wires, and associated preferences
4. Return the set M of input-to-output wire matchings

I'm having trouble proofing or disproving this algorithm correctly solves the problem. My goal is to show that if 2 data streams meet at the same junction then it leads to an instability in the matchings. I started by assuming the data streams meet on some arbitrary output wire and a downstream junction exists, but I haven't made any progress past that in showing an instability. The 2 source input wires will prefer this arbitrary output wire over their terminus wire, but there is always a place on this arbirary wire to place a junction such that the arbirary output wire prefers it over the other two junctions - then no instability can exist.

# Answer
> 3 votes
Your algorithm is clean and correct.

Here is an easy proof.

Let $\text{junction}(x,y)$ stand for the junction between input $x$ and output wire $y$. Let $\text{stream}(x,y)$ stand for the stream from input wire $x$ to output wire $y$, which must be switched at $\text{junction}(x,y)$.

The book has proved the Gale-Shapley algorithm must produce a stable and perfect matching. As an application, your algorithm must produce a stable and perfect matching between the input wires and output wires.

Suppose, for the sake of contradiction, an execution of your algorithm produces a matching $M$ that includes $\text{stream}(i,o)$ and $\text{stream}(i',o')$ that meet at some junction $J$. Since $\text{stream}(i,o)$ passes $J$, $J$ is either on the same input wire or the same output wire as $\text{stream}(i,o)$. Similarly, $J$ is either on the same input wire or the same output wire as $\text{stream}(i',o')$. Since input wires are disjoint to each other, $J$ cannot be on $i$ and $i'$ both. Similar, $J$ cannot be on $o$ and $o'$ both. So, $J$ must be either $\text{junction}(i,o')$ or $\text{junction}(i',o).$

* Suppose $J$ is $\text{junction}(i,o')$.

+ Since $\text{stream}(i,o)$ passes $J$, $J$ is upstream to $\text{junction}(i,o)$ on input wire $i$, i.e, $i$ prefers $o'$ to $o$.
    + Since $\text{stream}(i',o')$ passes $J$, $J$ is downstream to $\text{junction}(i',o')$ on output wire $o'$, i.e, $o'$ prefers $i$ to $i'$.

So $(i, o')$ is an instability with respect to $M$.
* Otherwise, $J$ must be $\text{junction}(i',o)$. Symmetrically, we will get that $(i', o)$ is an instability with respect to $M$.

However, $M$ is a stable matching. We have arrived at a contradiction. $\quad\checkmark$

---
Tags: matching
---


# Question
Title: Find distinct groups with no common parents
Given an array $arr$, element $arr\[i\]$ indicates its parent. If the element has no parent then $arr\[i\]=-1$. What is the optimal algorithm for finding the minimum number of groups such that no element in each group is a child node (whether directly or indirectly) of any other node in the same group.

# Answer
> 1 votes
*arr\[\]* can be considered a partial order, and the groups you're looking for are then called *antichains*. So, you're looking for a decomposition into a minimum number of antichains of the partial order represented by *arr\[\]*. According to Mirsky's theorem, the smallest achievable number of antichains is equal to the length of the longest chain -- that is, the longest path of descendants in the forest (set of trees) represented by *arr\[\]*. (It's impossible to do better than this, since every element in this longest chain needs to be assigned to a distinct antichain.)

That Wikipedia page also describes a neat way to actually construct an optimal set of antichains, based on the idea that if two elements have the same number of ancestors, neither of them can be an ancestor of the other. In short: Perform BFS on the forest defined by *arr\[\]*, starting from all root elements (you can do this by initially inserting all such elements into the queue); every layer (set of nodes at the same depth) constitutes one antichain.

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


# Question
Title: Should activation function be monotonic in neural networks?
A lot of activation functions in neural networks (sigmoid, tanh, softmax) are monotonic, continuous and differentiable (except of may be a couple of points, where derivative does not exist).

I understand the reason for continuity and differentiability, but can not really understand a reason for monotonisity.

# Answer
During the training phase, backpropagation informs each neuron how much it should influence each neuron in the next layer. If the activation function isn't monotonic then increasing the neuron's weight might cause it to have less influence, the opposite of what was intended. The result would be choatic behavior during training, with the network unlikely to converge to a state that yields an accurate classifier.
> 10 votes

# Answer
It is not necessary for the activation function to be monotonic. The best example of that is MISHactivation function which is non monotonic activation function and it out performs ReLU activation on various benchmarks.
> 1 votes

---
Tags: machine-learning, neural-networks
---


# Question
Title: What is the difference between Partition and Division?
While reading graph theory, I came across different definitions where they use partitions and divisions, I was wondering, are these terms same or different?

Can anyone explain me their difference in Set Theory?

I know this is a simple question but anyone hardly talk about it but they always make here a mistake.

# Answer
**I will explain this with an example :**

*Consider a set $S$ which contains a collections of sets with a constant k such that:* $$ S = \\{ \\{S\_1\\}, \\{S\_2\\}, \\{S\_3\\},\\{S\_4\\},..........\\{S\_k\\} \\}$$

### In Partition of Set S :

Then we can form the set again by

$ S=S\_1\cup S\_2\cup S\_3\cup S\_4...........\cup S\_k$

$where\ S\_i\cap S\_j = \phi$

$and\ i\neq j\ and\ i,j\in \mathcal{N} $

### In Division of Set S :

We just have this

$ S=S\_1\cup S\_2\cup S\_3\cup S\_4...........\cup S\_k$
> 0 votes

---
Tags: graphs, terminology, sets
---


title: Time complexity $O(m+n)$ Vs $O(n)$

text:
# Question
Title: Time complexity $O(m+n)$ Vs $O(n)$
Consider this algorithm iterating over $2$ arrays $(A$ and $B)$

size of $ A = n$

size of $ B = m$

Please note that $m \leq n$

The algorithm is as follows

```
for every value in A:
    // code

for every value in B:
    // code

```

The time complexity of this algorithm is $O(n+m)$ But given that $m$ is strictly lesser than or equal to $n$, can this be considered as $O(n)$?

# Answer
Yes:

$n+m \le n+n=2n$ which is $O(n)$, and thus $O(n+m)=O(n)$

---

For clarity, this is true **only** under the assumption that $m\le n$. Without this assumption, $O(n)$ and $O(n+m)$ are two different things - so it would be important to write $O(n+m)$ instead of $O(n)$.
> 39 votes

# Answer
Yes, since $n + m \leq 2n$ the algorithm is $O(n)$. However, you may wish to write $O(m + n)$ because it clearly shows which variables the algorithm depends on, and what each variable does to the complexity.
> 11 votes

# Answer
(expanding on my comment)

### Technically No

You need to be very careful here, as there is a difference between *algorithmic* time complexity and *runtime*. In the case you have described, the runtime may be O(n) but the algorithm itself is O(n+m).

This is because, without your *external* constraints, the algorithm's time complexity cannot be determined without knowing both `m` and `n`.

If you wanted to make the algorithm itself O(n), you would need to explicitly encode your external constraint that `m<n` within the algorithm itself. Adding a check that aborts if `m>n` would work.

### Unless...

The above does not hold if `m < n` *by definition* (ie it arises from a fundamental property of your data structures).

Say, for example, `A` is an array and `B` is an array composed of only the elements at the even indices of `A`. Then `m` is indeed `< n` by definition, and no check is required.

In cases like these the answer is yes, the algorithm is O(n). In fact, it would be 'incorrect' (assuming you are going for a tight upper bound) to say it is O(n+m) since the asymptotic performance depends entirely on `n`.
> 0 votes

---
Tags: time-complexity, arrays, big-o-notation, iteration, linear-complexity
---


title: Prove NLOGSPACE$\subset$PSPACE

text:
# Question
Title: Prove NLOGSPACE$\subset$PSPACE
Condidering the proof, NLOGSPACE$\subset$PSPACE

I wrote following proof:

NLOGSPACE = NSPACE$(\log n)$ $\hspace{15pt} \because$ Definition of NLOGSPACE

NSPACE$(\log n)$ $\subseteq$ DSPACE$(\log^2 n)$ $\hspace{15pt} \because$ Theorem(1)

We let $m = \log n$, then,

DSPACE$(m^2)$ $\subset$PSPACE $\hspace{15pt} \because$ Definition(2)

Therefore, NLOGSPACE$\subset$PSPACE.

Theorem(1): If $S$ is a space constructible function and $S(n) \ge \log n$, then NSPACE$(S(n)) \subseteq$ DSPACE$(S^2(n))$.

definition(2): PSPACE = DSPACE$(n)$$\cup$DSPACE$(n^2)$$\cup$DSPACE$(n^3)$$\cup$...$\cup$DSPACE$(n^k)$$\cup$...

But I am still not that sure if that "We let $m = \log n$" is ok, is this proving NLOGSPACE$\subset$PSPACE?

# Answer
> 1 votes
What would you think about a proof that says the following?

* $NP \subset DTIME(2^n)$
* let $m = \log n$, then $DTIME(2^n) = DTIME(m) \subset P$
* Therefore $P = NP$

Here, you have indeed $DPSACE(log^2n)\subset PSPACE$ but the argument is weird.

Also please note that Savitch's theorem already proves that $NPSPACE \subset PSPACE$, and you have the result you want, since $NLOGSPACE \subset NPSPACE$.

---
Tags: algorithms, time-complexity, space-complexity
---


title: Match unpaired points between two sets

text:
# Question
Title: Match unpaired points between two sets
I have two sets, let's call them C and T, of unpaired points, which could for example represent two types of cells. Hence, both points are drawn from the same underlying distribution, but the points in T underwent an additional process/function.

Although biologically debatable, I want to find the most similar points in the T set for each point in the C set. It does not need to be a 1:1 mapping, 1:n is also possible, because the sample sizes might be different.

How can I find such a mapping? Do you know any algorithms (or have other ideas) to achieve this? First, I thought it makes sense to span a graph in both sets by drawing edges between points which are below a certain distance. The distance for each set has to be such that the number of vertices with n edges are approximately the same in both sets. Afterwards I could match all points with k neighbors in set C, with all points with k neighbors in set T. Although I have not implemented this yet, I am unsure how efficient this will be.

# Answer
This is called the Assignment Problem, or equivalently Weighted Bipartite Matching.

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

---
Tags: graphs, matching, probabilistic-algorithms
---


# Question
Title: A very simple question about Admissible Heurisitcs
Given admissible heuristics f(s), g(s), h(s).

It is true that max(f(s), g(s), h(s)) is still admissible.. but is it still admissible if its max(f(s), g(s) + h(s)). I believe it is not admissible but I just want to make sure.

# Answer
No. Assume towards contradiction that it is true, then ignore $f$ completely (choose some $f$ which is constant)

Then, what your statement would say is that $h,g$ are admissible $\implies h+g$ is admissible.

In particular, for any admissible function $g$, choose $h=g$, and your statement implies $2g$ is admissible. Apply the statement again to get that $3g$ is admissible, and you can prove using induction that $kg$ is admissible for any constant $k$. However this is clearly not true, since you can choose $k$ to be big enough so $kg$ would over-estimate the search cost. In particular, choose $k=max(cost) + 1$, and then $kg$ would overestimate the cost everywhere.

Therefore its a contradiction and this statement is **false**
> 0 votes

---
Tags: search-algorithms, artificial-intelligence, search-trees, heuristics
---


# Question
Title: Showing that $K$ is dedicable is equivalent show that $Acc_{GNC}$ is decidable
1. If $K$ is a context-free language, then $K$ is a decidable language.
2. $\text{Acc}\_{\text{CFL}} = \\{〈G, w〉: G \text{ is a context-free grammar and G can generate } w\\}$ is decidable.

I am a bit confused. For me, showing that $K$ is dedicable is equivalent show that $Acc\_{GNC}$ is decidable. Where am I wrong?

# Answer
> 0 votes
Both statements are correct and thus are "equivalent" logically, even though it doesn't really mean anything. However, I will light the difference between the two statements.

## Statement 1

We need to show there **exists** a TM that decides $K$. That is, for a different $K$ we can find a different turing machine.

## Statement 2

We need to find **one** TM that is capable of deciding any language given its grammer. That is, here for different $G$'s we still use the same TM. In this sense, the second statement is stronger than the first, and it implies it.

---
Tags: context-free
---


title: Solve the following recurrence

text:
# Question
Title: Solve the following recurrence
I'm trying to solve this the recurrence : $$ T(n)=\begin{cases} 1, & \text{ if } n = 1 \\ T(n-1) +n(n-1), & \text{ if } n \geq 2 \end{cases} $$

# Answer
Since $T(n)=T(n-1)$, using induction we can prove that $T(n)= 1 + \sum\_{k=1}^n k(k-1) \le 2\sum\_{k=1}^n k(k-1)$

Now, calculating $\sum\_{k=1}^n k(k-1)$ gives us:

$\sum\_{k=1}^n k(k-1)=\sum\_{k=1}^n (k^2 - k) = \sum\_{k=1}^n k^2 - \sum\_{k=1}^n k$

Using this formula, we know that $\sum\_{k=1}^n k^2 = \frac{n(n+1)(2n+1)}{6}$, and its not hard to show that $\sum\_{k=1}^n k = \frac{n (n+1)}{2}$

Therefore, $T(n) \le 2\left(\frac{n(n+1)(2n+1)}{6} - \frac{n (n+1)}{2}\right) = O(n^3)$
> 1 votes

---
Tags: algorithms, complexity-theory, data-structures, recursion, discrete-mathematics
---


# Question
Title: Why do programming languages use call-by-value over call-by-name?
I am reading *Software Engineering 1: Abstraction and Modelling* by Dines Bjørner. One of the chapters talks a little bit about call-by-value vs call-by-name. In it, the author states that most programming languages use call-by-value, rather than call-by-name. But from what I have read in the chapter, it seems that call-by-name is a much safer method of calling functions.

For example, say we have a function like `f(x, y) = y * 3`, and we call it somewhere like `f(infinteLoop(), 6)`, where `infinteLoop()` is some function which never terminates. If we use call-by-name, we never have to call `infiniteLoop()` because `x` is never used in the body of `f`. But if we use call-by-value, we need to evaluate `infinteLoop()`, even though it will never be used in the body of `f`. This will cause the program not to terminate, of course.

It seems to me that call-by-name is both safer and more efficient (since we do not need to evaluate unused expressions). So for what reason do most (or *any* for that matter) programming languages use call-by-value instead of call-by-name?

# Answer
> 3 votes
There's a couple of factors which come into place. There can be performance costs to call-by-name, as well as difficulty with understandability in the presence of effects.

First of all, call-by-name can use exponentially more time than call-by-value, since it may have to evaluate an expression multiple times. Imagine calling `f(x) = x + x` when `x` takes a while to compute. In true call-by-name, the entire expression for `x` needs to be evaluated twice inside the body of `f`.

So in practice, instead of call-by-name, we likely would prefer *call-by-need*. We can instead cache the result of evaluating `x`, so that we don't have to compute it multiple times. This is what the programming language Haskell does (preceded by Miranda, Lazy ML). This solves the time complexity problem (as you may have intuited above, the time complexity is no worse than call-by-value), but it can also use much more space. This is because it may need large closures in order to delay evaluation. A machine integer uses a finite amount of space, but a Haskell Int could use arbitrarily large amounts, by accumulating a closure of computation that needs to be run. In the Glasgow Haskell Compiler, the garbage collector has special rules to specifically find and eliminate certain kinds of "space leaks" where we use excessive space via closures.

Even putting the theoretical aside, there are practical difficulties for implementing a call-by-name or call-by-need language on a traditional machine. Many programmers are used to using side effects in their program, such as input and output, and having their expressions run sequentially. In a call-by-name programming language, this is no longer the case, effects could be latent anywhere within an unevaluated expression, and only take effect when that data is examined. It took many years for the discovery that mathematical monads could be used as a sequencing interface. Prior methods for controlling input/output were difficult to use.

Call-by-value languages tend to also be able to be performant much more easily than call-by-name/call-by-need. Haskell has taken extensive optimization effort to run quickly, largely by being able to carefully introduce strictness to eliminate overhead of laziness. With laziness, a value of any type could be a closure: a complex allocated object and a pointer to remote code to run. This can require more allocations and more indirection to manipulate than machine integers and simple objects.

So, while we can't answer definitively why such languages aren't more popular, we can see that there has been plenty of complexity and research necessary to tackle, and so languages which used call-by-value have long had a head start.

# Answer
> 1 votes
Call-by-name was used in Algol 60, and it was let’s say “interesting”. Nowadays in the Swift language you can have “autoclosure” parameters: instead of evaluating an expression and passing the result, the actual expression itself is passed. It is evaluated every time the function that is called accesses the parameter. This allows for example implementing the `&&` and `||` operators as ordinary functions.

# Answer
> 0 votes
I'm reminded of that joke about playing all the right notes, but not necessarily in the right order.

Although there is often some room for rearrangement, the order in which operations appear in code, broadly correspond to the order in which they must be executed so as to produce a correct outcome.

Call-by-value is little more than a natural expression of this principle - the arguments of a call, which represent its inputs, are evaluated before the call itself.

It's difficult to grasp the basis on which any other system of evaluation is thought to be "more efficient" or "safer" by default.

Obviously it is possible to contrive situations in which it may seem to be more efficient if an argument were not immediately evaluated, but this often ignores the computational inefficiency of analysing the code and deciding whether such opportunities exist. In the example given, the two modes of evaluation actually don't produce equivalent outcomes - one locks up into an infinite loop unconditionally, the other only maybe so.

It also ignores the fact that we do not always need to simply tolerate inefficient orders of evaluation under the call-by-value regime - instead, the programmer can rework the code so that evaluation occurs *explicitly* in an efficient order. Any difficulties this entails, are likely to be less than the difficulty of working with a language where the order of evaluation is never consistent.

I also read Jason Carr's answer above with interest, and what it makes clear to me is that certain thinkers on the subject presuppose why programmers use 'calls', and presuppose that calls can or should be used only in the fashion of 'pure functions' which transform arguments into return values, with no 'side effects'.

Unfortunately, from the point of view of most programmers, the idea that manipulating global or shared state within a call is a "side effect", is as curious as the idea that drunkenness is a "side effect" of drinking beer. In fact, transformation of shared state is the *primary* purpose of most programs.

Calls are not only used for transforming arguments into return values, but also for orchestrating access to "shared state" that exists external to the current scope (and perhaps external to the current program or even machine).

Where shared state does exist, the programmer must be able to reason about when shared state is being read or rewritten, so as to coordinate that access correctly.

The full information about what shared state is involved, and terms on which such coordinated access to it is being done, is not normally available in the code itself, so the computer must simply do as the programmer says, in the order he says.

And that's why we come back around to call-by-value, because as I said above, it is simply a natural extension of the principle that the order of operations is important to the correctness of the program, and there appears to be no other sensible approach than to evaluate the arguments, before evaluating the calls which employ those arguments.

---
Tags: programming-languages
---


# Question
Title: Grammar for $\{a^n b^n c^m d^m \mid n \geq 1, m \geq 0\}$
I'm trying to understand how the construction of simple grammars works.

In my textbook, there's the following example I am supposed to find a grammar for:

> Let $L\_1= \\{a^n b^n c^m d^m \mid n \geq 1, m \geq 0\\}$ be a language over the alphabet $\Sigma = \\{a,b,c,d\\}$. Find a grammar $G = (\Sigma, N, S, P)$ \- where $N$ denotes the non-terminals, $S$ the start symbol and $P$ the production rules - such that $L(G) = L\_1$, i.e. the grammar $G$ generates the language $L\_1$.

These were my first thoughts analyzing the problem:

* We need to have the same number of $a$'s and $b$'s
* We need to have the same number of $c$'s and $d$'s
* There needs to be at least one $a$ and one $b$
* Examples of such a string: $aabbcccddd$, $ab$, $aabbcd$

Furthermore, let $\lambda$ be the empty symbol.

The start symbol $S$ should map to something like: $$ S \rightarrow XY$$

Then $$X \rightarrow aZb, \\; Z \rightarrow X | \lambda$$ $$Y \rightarrow cYd | \lambda$$

Would something like that work? I'm confused because the textbook presented similar grammars and the production rules almost never used the empty symbol ($\lambda$).

Is it possible to construct this grammar without using $\lambda$?

# Answer
You can always write a grammar without $\lambda$, unless the language itself includes $\lambda$. In that case, you will need the single production $S\to\lambda$ (where $S$ is the start symbol).

There's a simple algorithm for removing $\lambda$ from grammars. First, figure out which non-terminals might produce $\lambda$. (These non-terminals are called "nullable non-terminals".) Then, for each nullable non-terminal and for each production in which it occurs, add a new production which is the same but without the non-terminal. (If the non-terminal appears more than once in the same production, do this for each occurrence of the non-terminal.) Keep doing this until no more additions are possible. Then remove all of the productions with empty right-hand sides, except the empty production for the start symbol (if there is one).

Applying this algorithm to your example, we first find that $Y$ and $Z$ are nullable, while $S$ and $X$ are not. So then we need to add additional productions:

* From $X\to a Z b$, add $X\to a b$.
* From $Y\to c Y d$, add $Y\to c d$.
* From $S\to X Y$, add $S\to X$.

That gives us:

$$S\to X Y, S\to X\\ X\to a Z b, X\to a b \\ Z\to X, Z\to \lambda \\ Y\to c Y d, Y\to c d, Y\to \lambda $$ We then delete the two empty productions, leaving: $$S\to X Y, S\to X\\ X\to a Z b, X\to a b \\ Z\to X \\ Y\to c Y d, Y\to c d $$ At this point, we might note that $Z$ is totally redundant. We can simplify the grammar by just substituting its right-hand side in the only place where it is used: $$S\to X Y, S\to X\\ X\to a X b, X\to a b \\ Y\to c Y d, Y\to c d $$
> 0 votes

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


title: Modular exponentiation running time

text:
# Question
Title: Modular exponentiation running time
I read on Wikipedia that modular exponentiation can be done in polynomial time. I've a few questions regarding it (sorry if they seem a bit easy – I'm not a comp sci student).

1. Is it poly time only for base 2, i.e in binary or will it remain poly time algorithm even if i run it in decimal system i.e base 10?
2. If I'm calculating $(a^b) \bmod p$, where $1\<a\<11$, $1 \< b \leq (p-1)/2$, and we run this modular exponentiation at most $p/2$ times, all this being done in decimal base 10 system, will it still be poly time?
3. Even if this is poly time, and this is a big IF, can this process actually be completed in reasonable time in terms of the real worldly time?

# Answer
> 1 votes
With regards to (3), there's a fairly simple algorithm to compute large exponents.

```
exp(a, b) =
  if b is even
     let half = exp(a , b/2)
     return half * half
  else
    return a * exp(a, b-1)

```

This will be logarithmic in the magnitude of $b$, meaning the number of multiplications is linear in the number of bits used to represent $b$. It's also a very general algorithm: it works for normal exponentiation, matrices, modular arithmetic, etc. The complexity will change depending on the complexity of your multiplication operation.

# Answer
> 0 votes
First of all, by the direct method, you have to multiply $b-1$ times the a and take a modular reduction.

1. As stated in Wikipedia, the mathematical calculation are performed for any base $b$. In complexity theory the base is constant doesn't affect the class of the algorithm; the time is $\mathcal{O}(log\\; exponent)$, for any base.
2. See,1.
3. Bigger exponent doesn't change the class. For polynomial time algorithms, sometimes have huge multipliers that they can be slower than exponential algorithms, up to some $n\>0$, eventually, we will have the expected result. To determine the exact running time, in general, you have to mention the code, the compiler, the CPU and memory, number of cpus/cores and the exponent and the base itself. Than you can talk bout a bit more exact timings.

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


# Question
Title: If $ \text{NV}_{\text{TM}}$ is decidable, then $A_{TM}$ is decidable?
It seems that $ \text{NV}\_{\text{TM}} = \\{〈N〉: N \text{ a Turing-Machine and } L(N) ≠ ∅\\}$ is not decidable.

Here is a proof:

> Suppose that $\text{NV}\_{\text{TM}}$ is decidable with the Turing-Machine $R$.
>
> We can define for each Turing-Machine $M$ and each entry $w$ a Turing-Machine $S\_{M,w}$ as follow:
>
> $S\_{M,w} :=$
>
> 1. If $x \not= 0$, then reject $x$;
> 2. If $x = 0$, then simulate $M$ on $w$ and accept if and only if $M$ accepts $w$
>
> Consider now the Turing-Machine
>
> $T :=$
>
> 1. Input $〈M, w〉$:
> 2. Construct the machine $S\_{M,w}$ and product $〈S\_{M,w}〉$;
> 3. Simulate $R$ on the input $〈S\_{M,w}〉$ :
> 4. If $R$ accepts $〈S\_{M,w}〉$ then accept $〈M, w〉$
> 5. If $R$ rejects $〈S\_{M,w}〉$ then reject $〈M, w〉$

I am a bit confused.

1. How it is possible to simulation $R$ on the input $〈S\_{M,w}〉$
2. The proof says nothing else. Supposing that $ \text{NV}\_{\text{TM}}$ decidable should implies that $A\_{TM}$ is also decidable. How with that proof can we say that $A\_{TM}$ is dedicable (Contradiction)?

# Answer
## For the first part

The idea behind the proof is to assume towards contradiction that it is decidable. Then, there must be that turing machine $R$. Its a real turing machine, and you can write its code if you want. Therefore, you can simulate it on any input you would like, and in particular, you can on $\langle S\_{M,w}\rangle$ too.

## For the second part

Notice what $T$ does: It takes an input $\langle M, w\rangle$ and **decides** whether $w\in L(M)$ or not. That is, $T$ decides $A\_{TM}$ in contradiction.
> 0 votes

---
Tags: turing-machines, undecidability
---


# Question
Title: Is it true that $ 2^{O(3k)} = 2^{O(k)} $?
Is it true that $ 2^{O(3k)} = 2^{O(k)} $?

But It should be different from $ O(2^{k}) = 2^{O(k)} $ ?

I will be happy for simple explanation.

Thanks.

# Answer
$\mathcal{O} (3k) = \mathcal{O} (k)$ because $\mathcal{O} (k)$ can be defined like this:

$$ \tag{1} d = \mathcal{O} (k) \implies d \le Ck , $$ for some constant $C\>0$ and for all $k$ larger than some threshold, and similarly $\mathcal{O}(3k)$ would be defined as:

$$\tag{2} d\_3 = \mathcal{O}(3k) \implies d\_3 \le C\_3 (3 k), $$

for $C\_3 \> 0$ and for all $k$ larger than some threshold.

Now remember that $C$ and $C\_3$ are positive, so $3C\_3 \> C$, which means that **if $d\_3 = \mathcal{O}(3k)$ then it must also be $\mathcal{O}(k)$.**

Then since $2^k$ is a monotonic function, **we also have that $2^{\mathcal{O}(3k)} = 2^{\mathcal{O}(k)}$.**

Some will argue that specifying the extra constant of "3" is redundant and formally improper, but you might still find that constant explicitly written in some papers, especially by people that don't know the above definition and tend to use big-O notation with (some would say regrettable) looseness.

## The bottom line: If you know the constant hiding under the Big-O is 3, you might as well just say $d \le 3k$ instead of $d=\mathcal{O}(3k)$.

---

**You've added a new question to your post after two of us already answered the first one. For the second question:**

$2^{\mathcal{O}(k)}$ gives us everything of the form $2^l$ where $l \le Ck$ under the conditions of Eq. 1.
By monotonicity of the function $2^l$ we have everything smaller than $2^{Ck} = (2^C)^k$ under similar conditions.

Let's consider the example where $C=2$.

* Your question becomes whether or not $\mathcal{O}(2^k) = \mathcal{O}(4^k)$, but since there is no constant $C$ such that $4^n \le C 2^n$, it is not true that $\mathcal{O}(2^k) = \mathcal{O}(4^k)$.
* Therefore it is also not true that $\mathcal{O}(2^k) = \mathcal{O}(2^{Ck})$ and:
* it's also not true that $\mathcal{O}(2^k) = 2^{\mathcal{O}(k)}$.

## Conclusion: $\mathcal{O}(2^k) \ne 2^{\mathcal{O}(k)}$ in general.
> 2 votes

# Answer
Yes:

$O(3k) = O(k)$, and thus $2^{O(3k)}=2^{O(k)}$.

For a rigorous proof, try using the definition of big-O and the monotonicity of the function $f(x)=2^x$.

---

### Rigorous proof of the fact

(The statement the OP asked immediately follows because of the equality of the sets $O(3k)$ and $O(k)$) We will prove a stronger statement.

**Theorem:** If $h(n)=O(g(n))$, and $f$ is a monotonically increasing function, then $f(h(n)) \in f(O(g(n)))$.

**Proof:** since $h(n)=O(g(n))$, then there is some $c\>0$ and $n\_0\in \mathbb{N}$ such that for all $n\>n\_0$, $h(n)\le cg(n)$. Since $f$ is monotonically increasing, then $f(h(n))\le f(cg(n)) \in f(O(g(n)))$. Thus $f(h(n)) \in f(O(g(n)))$.
> 1 votes

# Answer
1. For $C \gt 0$ we have $C\cdot O(g)=O(C\cdot g) = O(g)$.
2. Taking non negative case, if $f(n) \in O(2^n)$, then, in appropriate conditions, $f(n)\leqslant C 2^n= 2^{n+\log\_2 C} \leqslant 2^{2n} \in 2^{O(n)}$.

On other hand $2^{2n} \notin O(2^n)$. So, we have only $O(2^n) \subset 2^{O(n)}$.
> 1 votes

---
Tags: asymptotics, big-o-notation
---


# Question
Title: Given N positive integers are they the integers 1-N : What is the relationship between this problem and NP?
Here’s the **decision problem**:

**Suppose I have N positive integers encoded in base-2 (as oppose to unary)**

**Are these integers precisely the integers 1-N in some order?**

This is related to the Hamiltonian path problem which is NP-complete

Given a graph with N vertices you can nondeterministically walk a path of length N

If you could decide whether or not the sequence is precisely the integers 1-N in some order then you could decide whether or not the path is Hamiltonian

Hence the decision problem is related to the Hamiltonian path problem

What then is the relationship to NP?

Is it NP hard?

Is it NP complete?

# Answer
> 2 votes
Recognizing that a path is a Hamiltonian path is easy. Finding one in the first place may be hard (the number of candidates is large).

The defining property of problems in NP is that verifying a solution is "easy" (in P). Your problem is one part of verifying a solution of a Hamiltonian path problem. (You also have to verify that the path is a subgraph of the input graph.)

---
Tags: np-complete, np-hard, np, decision-problem
---


# Question
Title: Context free grammar transformation to Normal Form
I found a task where you need to transform context free grammar to normal form. I'm a High Shcool student at this moment. But my Brother learning this at the university. He don't have much time to explan this, this is why I'm writting this question.

This is the task description: A chainless G grammar equivalent to G' grammar, all symbols of which can be used.

And the task is:

```
G : S → BC | DB
A → BD
B → b | D
C → CD | BC
D → bC | a | bB

```

If anybody can help me, please write a comment. Thanks :)

# Answer
If you are trying to convert the grammer into Chomsky Normal Form, consider applying this algorithm that can create a new normal grammer from an existing non-normal one.
> 1 votes

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


# Question
Title: Model Counting for Sum of Conjunctive Formulas
## Problem:

Let $X=\\{x\_1, ..., x\_N \\}$ be a set of binary variables. Each variable can be assigned to either $0$ or $1$ so there are $2^N$ possible assignments.

**Input:** We are given a positive integer $C$ and a set of binary functions $F=\\{f\_1,...,f\_M\\}$ where each function is defined as a simple conjunction of some subset of $X$. That is, each $f\_i \in F$ is defined as $f\_i(X) := \prod\_{x \in X'}x$ for some $X' \subseteq X$.

**Output:** The number of assignments to variables in $X$ such that $\sum\_{i=1}^M f\_i(X) = C$.

## Question:

Do you know of a polynomial-time algorithm that solves this problem for a bounded value of $C$?

Any ideas or pointers to references would also be greatly appreciated.

It is OK if the complexity is bounded with respect to e.g. some constant $D$ which could be the maximum size of $X'$, that is, the maximum number of variables in the product of any function $f\_i \in F$.

## Observations:

When $|X'|=1$, that is, when each function $f\_i \in F$ can only have one variable, then the problem can be reduced to the counting version of the subset sum problem and can be solved in $\mathcal{O}(N\cdot C)$ time using an modified version of a dynamic programming algorithm for solving subset sum.

# Answer
> 1 votes
When $C = 0$ and each $f\_i$ depends on two inputs, your problem is equivalent to #2-MONOTONE-SAT, which is #P-complete, see for example this question on cstheory.

---
Tags: algorithms, combinatorics, counting
---


# Question
Title: Derive Turing Machine with high level description
So I have been going over Turing machines for my revision and came across an old worksheet with the question:

> Derive a Turing Machine using high level description with stages to decide on the following language {\<,\>| }.

I thought I understood Turing machines and CNF until I came across this but I can't figure it out. There is no answer sheet for this so I was wondering could someone answer it with steps to guide me through it so I can understand?

# Answer
> 0 votes
Its easy to check that $C$ is given in Chomsky Normal Form, because you just have to iterate through the production rules and make sure each one of them satisfies the definitions for being a CNF production.

Then, the harder part is deciding whether $C$ can produce $s$ or not. Notice, that a CNF will derive a word with length $n$, in exactly $2n-1$ steps. (every production will either transform a variable to the letter corresponding to it, or will create one new variable) Keeping this in mind, we can just iterate through all production chains that contain $2n-1$ steps (for $n=|s|$), and check whether we saw $s$ or not. If $s\in L(C)$, then we will see it, since $s$ can be derived with $2n-1$ steps. And if $s\notin L(C)$ we won't see it, therefore the algorithm is correct.

---
Tags: turing-machines, normal-forms
---


# Question
Title: Complexity of generating non-uniform random variates
What can we say about the complexity of generating (negative) binomial and (negative) hypergeometric random variates? In particular, it is possible to generate (negative) binomial and (negative) hypergeometric variates in (expected) constant time (i.e. independent of the distribution parameters)?

There is quite a bunch of literature; however, it’s hard to understand a lot of the papers. Moreover, I found some statements that seem contradictory to me (probably due to wrong understanding).

For example, Stadlober (or similar here) mentions a "generalization \[of the ratio-of-uniforms approach\] to any unimodal discrete distribution". The ratio-of-uniforms approach has been called *uniformly fast*, which is a synonym for constant time, I suppose (?). That would mean that we can generate random variates for each discrete distribution in (expected) constant time.

However, in another paper, I found the following theorem: On a RAM with word size $w$, any algorithm sampling a geometric random variate $Geo(p)$ with parameter $p \in (0,1)$ needs at least expected runtime $\Omega(1 + \log(1/p)/w)$.

Apparently, this means that it is not possible to generate negative binomial variates in time independent of the distribution parameters.

# Answer
The binomial, negative binomial, and hypergeometric distributions are discrete distributions. Knuth and Yao (1976) gave complexity results for discrete distributions in general. Given a stream of i.i.d. unbiased random bits, any algorithm that samples from a discrete distribution will require at least—$$b = -\sum\_{x\in\Omega} \mathbb{P}(X=x)\*\log\_2(\mathbb{P}(X=x))$$random bits on average to sample a variate $X$ from that distribution (where $\Omega$ is the distribution's support), and they gave an algorithm that comes within 2 bits of this lower bound (and showed that coming within 2 bits is the best possible for any algorithm).

The case of continuous distributions such as the normal distribution is more complicated, but Devroye and Gravel gave complexity results for sampling a continuous variate to a desired accuracy, given a stream of i.i.d. unbiased random bits, using Wasserstein distance as the accuracy metric.

I also want to note one more thing. If the distribution of $X$ has a continuous and bounded quantile function (inverse cumulative distribution function) $F^{-1}$, I suspect that the bit complexity of sampling $X$ also depends on the modulus of continuity of $F^{-1}$, call it $\omega(h)$. In this sense, Lipschitz continuous quantile functions (where $\omega(h) = O(h)$) are the simplest cases of such functions and in that case it's simple to describe an algorithm to sample $X$ to a desired accuracy. For such functions, the algorithm uses—$$ceil(\ln(\max(1, L))-\ln(\epsilon))/\ln(\beta))$$random digits, where $L$ is the Lipschitz constant, $\epsilon$ is the desired accuracy, and $\beta$ is the digit base (such as 2 for binary). I suspect that with other moduli of continuity, the complexity will be as follows: $$ceil(-\ln(\omega^{-1}(\epsilon))/\ln(\beta)).$$

REFERENCES:
> 4 votes

---
Tags: time-complexity, sampling, random-number-generator
---


# Question
Title: $\{<M>: M \text{ is a finite automata and L(M) contains a word of form } a^ib^j\}$ is decidable?
How can we show that the language $K = \\{\<M\>: M \text{ is a finite automata and L(M) contains a word of form } a^ib^j\\}$ is decidable?

# Answer
Let $\hat M$ be the DFA for the language $L(a^\*b^\*)$ (aka, words of the form $a^ib^j$).

Construct the intersection DFA between $M$ and $\hat M$, and call it $M'$. Now, check if $L(M')=\emptyset$. If it does, reject. Otherwise, accept.

Here is useful material about intersection DFA and about checking the empty-ness of the DFA language
> 1 votes

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


# Question
Title: Prove by contradiction that the language with unequal number of a's and b's is not regular
Consider the language $$L = \\{w \mid w \text{ has an unequal number of a’s and b’s}\\}$$ where Σ = {a, b}. Prove that L is not regular. Hint: Try proof by contradiction.

Would this be the right Answer:

L = {a^m b^n | m \< n} U {a^m b^n | m \> n}

Looking at this we can tell that a is more than b or a is less than b. They depend on each other. Thus we can tell that language L is not regular, because we can conclude dependency. Dependency needs a stack to compare to one another. Finite automata does not have a stack.

# Answer
What you explained cannot be called a formal proof. Its only within the scope of intuition. A formal proof needs formal arguments, using theorems and or lemmas along the way.

Anyways, try to think of $L^c$ (the complement of $L$). Is this language regular? What is the connection between $L^c$ and $L$ in those terms?
> 1 votes

# Answer
Assume the language is regular, then it can be implemented using a finite state machine with k states.

If you parse a string starting with a^k then you must enter some state X twice, parsing a^j for some 1 \<= j \<= k to get from X back to X. You could remove that string a^j from your input and reach the same state parsing the whole string.

Now take the strings a^(k+j)b^k and a^kb^k. One is in the language, the other isn’t, but they end in the same final state, so they must be both in the language of both not in the language.

Of course that’s just the pumping Lemma...
> 0 votes

---
Tags: regular-languages, finite-automata, closure-properties
---


# Question
Title: Construct PDA for $Σ^* -\{(a^nb) ^n, n>0\}$
I want to construct a PDA for $Σ^\* -\\{(a^nb) ^n, n\>0\\}$ where $Σ=\\{a, b\\}$. Here is my try: I know that context-free languages are closed under union operation. Also I know how to make a PDA for union. So I tried to decompose the given language to some parts. For example, the language of the strings starting by $b$, the language of strings ending with $a$, the language of strings containing $bab$ as a substring. I made a context-free grammar for these languages. Then I made PDAs based on each grammar and I combined them to get a PDA for the union of them. But I know that the union of these languages does not cover all strings in the given language. Could you help me find what I'm missing and how to make a context-free grammar for that?

# Answer
> 1 votes
If a word is not of the form $(a^nb)^n$ for $n \> 0$, then one of the following must happen:

* The word is not of the form $(a^\*b)^+$, i.e., it is either empty or ends in $a$.
* The word is of the form $a^ib(a^\*b)^\*a^jb(a^\*b)^\*$ for some $i \neq j$.
* The word is of the form $a^nb (a^\*b)^k$, where $n \neq k+1$.

Each of these can be checked by a PDA or generated by a CFG. It might help to break a condition of the form $i \neq j$ into two alternatives, $i \> j$ and $i \< j$.

To see why this case distinction holds, let us assume that the word is of the form $(a^\*b)^+$. We can write it as $$ a^{i\_1} b a^{i\_2} b \cdots a^{i\_m} b. $$ The word is of the form $(a^nb)^n$ if $i\_1 = \cdots = i\_m = m$, which is equivalent to $$ i\_1 = i\_2 \text{ and } i\_1 = i\_3 \text{ and } \cdots \text{ and } i\_1 = i\_m \text{ and } i\_1 = m. $$ Hence the word is *not* of the form $(a^nb)^n$ if $$ i\_1 \neq i\_2 \text{ or } i\_1 \neq i\_3 \text{ or } \cdots \text{ or } i\_1 \neq i\_m \text{ or } i\_1 \neq m. $$ The case $i\_1 \neq i\_j$ is handled by the second bullet above, and the case $i\_1 \neq m$ is handled by the third bullet.

(Thank you to Hendrik Jan for help with simplifying the cases.)

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


# Question
Title: Why if L and ¬L (Complement of L) are turing-recognized both are turing-decidable?
I can't understand this theorem: If both L and L complement are turing-recognized, both are turing-decidable

Proof:

* w is M input
* if w ∈ L then M1 accepts w and M accepts w
* if w ∉ L then M2 accepts w and M rejects w

M is a TM containing M1 and M2.

# Answer
I will try to explain it in simpler terms.

If $L$ is Turing recognizable, there exists a TM $M\_1$ that halts and accepts any input string $w \in L$. It is not guaranteed to halt on any input string $w \notin L$.

If $\bar{L}$ is Turing recognizable, there exists a TM $M\_2$ that halts and accepts any input string $w \notin L$. Similarly to above, $M\_2$ is not guaranteed to halt on any input string $w \in L$.

Now, for every $w$ we have two options: either $w \in L$ or $w \notin L$. Therefore for any input string $w$, exactly one of these machines will halt and accept. This allows us to construct the decider described in you proof. Create a machine $M$ that simulates $M\_1$ and $M\_2$. With $w$ as input, accept $w$ if $M\_1$ accepts, reject if $M\_2$ accepts. This machine is a decider for $L$ and therefore $L$ is decidable.

To prove $\bar{L}$ decidable as well, you could apply the same logic, but it is sufficient to point out that decidable languages are closed under complement.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: my new sorting algorithm, what should my upper bound be?
I just thought this up while walking after typing up a knapsack with repetition implementation in Python.

I want to teach computer science so I talk to myself a lot pretending to talk to students.

So in my imaginary lecture for merge sort, I used the example of an unshuffled deck of cards.

But then it hit me that, "With cards, I know what high and low are so I can just have a grid that is 4 * 13 with spades as first row, then hearts, then clubs then diamonds".

That would take exactly O(n) where n = 52 to sort the pile if I pick a card and put it in its place since each operation takes O(1) + O(1)

So then I thought, why can't I do this for a sort of any array with the caveat being that all values need to be distinct.

I can find the minimum and maximum in O(n), remember the indices and truncate the input array by 2 by deleting these to make array called rem for remaining.

Then I make an array of size (maximum - minimum) as the grid with minimum at index 0 and maximum at array.length - 1 and initialize all values to some value outside the range of minimum to maximum.

Then I remember what minimum and maximum are for the following operations.

Iterate rem from index 0, and for each element, calculate: index = element\_value - minimum

Then put the element in the grid at position index.

Repeat for the entire rem array.

Calculations are done in constant O(1) time as well as insertions for n times for total O(n).

Now make a new array final that has length of input array.

Now traverse the grid and transfer to array final all valid values that are not equal to the initialized value outside the range.

This could take a super long time if the difference between maximum and minimum far exceeds input size n so when I do maximum - minimum, I have to set some sort of upper bound to this difference before it defaults to an O(nlogn) merge sort or an even faster Tim sort that is built into Python.

But say the initial range is min = 0, max 20 and n = 10. That final operation would take O(2n) which is still big-O of O(n). If the range is min = 0, max =100 and n =10, it would take O(10n) which still defaults to O(n)?
Calculating O(nlogn) for the last example, I get:

(10) * log\_2(10) = approx. 35?

Which means max-min \<= 35 I can match the speed of merge sort?

Edit:

Even if there are repeated values in the input array, I could have have a 2D array for the grid or a list of tuples in the case of Python and keep adding to it.

```
tup = tup + (repeat_val,)

```

And for an input array with consecutive values, this would be way faster wouldn't it?

# Answer
> 2 votes
It looks like the algorithm you are describing is called counting sort.

This algorithm works in $O(n+k)$ where $n$ is the number of items in the input, and $k$ would be their range: $k=max - min$.

This algorithm is indeed better in computational time complexity than mergesort when you restrict $k$ to be small enough. For your examples, you "fixed" a value for $n$ and $k$, which makes no sense to compute the big-O notation on. The big-O describes the algorithm in its full behaviour, and is an upper bound for any "fixed" value you would give.

As a side note, this algorithm is not a comparison-based sorting (sorting **only** by comparing numbers), and can only sort natural numbers. Actual comparison-based sorting algorithms (like mergesort) must take at least $\Omega(n\log(n))$, but are capable of sorting any list, and not just natural numbers.

---
Tags: sorting
---


# Question
Title: Sorting an array where the largest element appears once, the second largest appears twice and in general the $k$-th element appears $2^{k-1}$ times
I need to find a sorting algorithm to sort an array where the the $k$-th element appears $2^{k-1}$ times in $O(2^k)$.

It also given there are $k$ distinct elements in the array, hence there are $1 + 2 + 2^2 + \dots + 2^{k-1}=2^k-1$ elements in the array. So I actually need to sort the array in $O(n)$ where $n$ is the array size.

Not sure how to use the known quantity of each element to sort faster.

Any help is appreciated.

# Answer
If I understand correctly the title (which is a bit clearer than the post itself), an example of such an array would be $\[1, 4, 1, 2, 1, 2, 5, 2, 1, 1, 4, 1, 2, 1, 1\]$.

If that's the case, you can:

* Count the number of occurrences of each value, with a hashtable for example;
* Sort the unique values with descending order of occurrences;
* Recreate the sorted array by repeating each value by the number of occurrences.

This algorithm is indeed in time complexity $O(n)$, since the array contains only $\log\_2 (n+1)$ unique values. That means that even the worst case of operations in the hashtable is in complexity $O((\log n)^2)$, and sorting the unique values array can be done in $O(\log n \log \log n)$. The last step is done in $O(n)$.
> 1 votes

---
Tags: data-structures, sorting
---


# Question
Title: Existence of non-context free but decidable languages
I've been reading the decidablity and undecidability chapters in Sipser's "Intro to Theory of Computation" however I could not find an explanation on the existence of a language that is both non-context free and decidable.

The only reference to this was a simple language hierarchy diagram showing where the decidable/recognisable bounds were in relation to language types.

I'm unsure as to how I should approach this but I've thought about proving this by diagonlisation:

* Let $M$ be the set of all decideable Turing Machines, and $L$ the set of all languages that are context-free. (Assume finite alphabet)
* By drawing up and filling the table where each language corresponds to a Turing Machine, I was hoping that I could find a contradiction in some $m \in M$ where there is no corresponding language $l \in L$.

I know that this will not work as both $M$ and $L$ are countable.

Any ideas on how I should approach this?

# Answer
You could simply consider the language $L = \\{a^k | k \text{ is a prime number }\\}$. This is not a context free language, but surely this is decidable by a Turing Machine that checks if the length N of the input is not divisible by any number between 2 and N-1 .
> 2 votes

# Answer
I had not the enough reputation in this community to leave a comment on @Umamg's answer; so, I try to complete Umang's answer in mine.

One way to show that the language $L=\\{a^p: \text{p is a prime number}\\}$ is not context-free is to use pumping lemma for CFLs in the following way:

If $L$ was a CFL, then given an arbitrary long string in this language, say $a^p$ with $p$ being greater than the pumping length of $L$, this string would be decomposed into five parts $uvxyz$ with $|vy|\geq 1$ and so that for any $i\geq 0$ the string $uv^ixy^iz$ would belong to $L$.

Let $l:=|vy|$, then the above discussion shows that all the following strings are part of the language $L$: $$a^p, a^{p+l}, a^{p+2l}, \ldots, a^{p+nl}, \ldots$$

That is, the set of prime numbers contains an infinite arithmetic progression which is impossible since the number $p+pl$ is divisible by p.
> 1 votes

# Answer
There are two quick answers within easy reach of undergrad courses:

1. CFL ⊊ CSL ⊊ R
2. CFL ⊊ P ⊊ R

Basically, "all" of complexity theory happens "between" CFL and R (with some notable exceptions). Just have a look at the complexity zoo and note how far down CFL is, and how far up R.
> 0 votes

# Answer
A direct diagonalization argument is very much usable here (even though a somewhat unorthodox choice, as we have "more natural" separating examples available to us).

We can construct in a straight-forward way a notation system for context-free grammars, which then lifts to a notation system $(L\_w)\_{w \in \Sigma^\*}$ for the context-free languages. We can then define the diagonal language $L\_\Delta = \\{w \in \Sigma^\* \mid w \notin L\_w\\}$. The usual proofs that each context-free language is decidable are all uniform in the grammar, and thus give us that $L\_\Delta$ is decidable. By construction, $L\_\Delta$ is not context-free.

Everything in the preceeding paragraph remains true if we replace "context-free" by "context-sensitive".
> 0 votes

---
Tags: formal-languages, computability
---


# Question
Title: How is Hypergraph Isomorphism (HI) reduced to Graph Isomorphism (GI) in polynomial time?
This question states that the problem of Hyper-graph Isomorphism is equivalent to Graph isomorphism. I have not been able to find a description of the reduction so I am wondering how that might work and what is its complexity. If I understand the post in the link correctly, the reduction has to be polynomial in order for the Hyper-graph isomorphism solution to inherit the same complexity as the Graph-isomorphism problem. Is the reduction only valid for a special case of the Hypergraph isomorphism problem or in general?

# Answer
> 4 votes
A description is given in the first paragraph of \[1\], where HI stands for Hypergraph Isomorphism and GI for Graph Isomorphism:

> Given a pair of hypergraphs $X=(V,E)$ and $X'=(V',E')$ as instance for HI, the reduced instance of GI consists of two corresponding bipartite graphs $Y$ and $Y'$ defined as follows. The graph $Y$ has vertex set $V \uplus E$ and edge set $E(Y) = \\{\\{v,e\\} \mid v \in V, e \in E, v \in e\\}$, and $Y'$ is defined similarly. Here, $C \uplus D$ denotes the disjoint union of the sets $C$ and $D$. It is easy to verify that $Y \simeq Y'$ if and only if $X \simeq X'$ assuming that $V$ can be mapped only to $V'$ and $E$ can be mapped only to $E'$. This latter condition is easy to enforce.

The other direction is trivial as every graph is also a hypergraph.

---

\[1\] Arvind, Vikraman, Bireswar Das, Johannes Köbler, and Seinosuke Toda. "Colored hypergraph isomorphism is fixed parameter tractable." Algorithmica 71, no. 1 (2015): 120-138.

---
Tags: complexity-theory, graphs, reductions, polynomial-time
---


# Question
Title: Proof regular languages are closed under homeomorphism
Let $\Sigma\_1 , \Sigma\_2$ be alphabets. Let $L\subseteq \Sigma\_1^\*$ be a regular language, and let $ h:\Sigma\_1^\* \rightarrow \Sigma\_2^\* $ be a homomorphism.

Proof $h(L)$ is regular.

I have written a proof using induction over the number of operands in the regular expression $r$ such that $L = L(r)$, **that there exists a regular expression $r'$** such that $L(r') = h(L)$.

I divided it to three cases:

1. $r=r\_1 \cup r\_2$
2. $ r= r\_1r\_2$
3. $ r =r\_1^\*$

Since functions union might not always be a function (i.e $f(1)=1$, $g(1) =2$ $\rightarrow f\cup g$ not a function) **I would like to get your opinion for the union case,** to verify I didn't do anything wrong there - especially in lines $5,6,7$:

1. $w\in h(L) \Leftrightarrow w = h(\sigma\_1 \dots \sigma\_n)\in h(L) \wedge \sigma\_1 \dots \sigma\_n \in L \Leftrightarrow $
2. $\sigma\_1 \dots \sigma\_n \in L(r\_1 \cup r\_2) \Leftrightarrow $
3. $\sigma\_1 \dots \sigma\_n \in L(r\_1) \cup L(r\_2) \Leftrightarrow $
4. $\sigma\_1 \dots \sigma\_n \in L(r\_1) \vee \sigma\_1 \dots \sigma\_n\in L(r\_2) \Leftrightarrow $
5. $h(\sigma\_1 \dots \sigma\_n) \in h(L(r\_1)) \vee h(\sigma\_1 \dots \sigma\_n) \in h(L(r\_2)) \Leftrightarrow $
6. $h(\sigma\_1 \dots \sigma\_n) \in h(L(r\_1)) \cup h(L(r\_2)) \Leftrightarrow $

Now, using the induction hypothesis, since $r\_1$ and $r\_2$ has less operands,

7. $h(\sigma\_1 \dots \sigma\_n) \in L(r\_1') \cup L(r\_2') \Leftrightarrow $
8. $w \in L(r\_1' \cup r\_2') $

**Is this a valid proof for this case?**

# Answer
This proof looks correct. You can shorten it a bit (it doesn't need to be so descriptive), and you would get the following proof:

$h(L)=h(L(r\_1\cup r\_2))=h(L(r\_1)\cup L(r\_2)) = h(L(r\_1))\cup h(L(r\_2)) = L(r'\_1)\cup L(r'\_2)=L(r'\_1\cup r'\_2)$

Where the transition $h(L(r\_1)\cup L(r\_2)) = h(L(r\_1)) \cup h(L(r\_2))$ can be shown for any function $h$ (not necessarily a homeomorphism!).
> 1 votes

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


# Question
Title: What are the differences between Oracle Turing Machine and PAC?
I am having difficulty understanding the difference between PAC and Oracle Machines. I cannot compare these two in terms of uncertainty and physical effort.

The degree of uncertainty we can tolerate in a system has been discussed ever since Turing. His oracle machines answer questions with maximal uncertainty, and zero physical work, because they are oracles. They don't have to justify their answers.

His automatic machines, or a-machines, are what we now call standard TM. In the probabilistic version, there is no new class of functions that we can compute which we cannot compute with deterministic TM. The Probabilistic TM can decide which route to take depending on probabilities assigned to its transitions. In the simplest case of binary branching at every state and total random choice, it flips a coin about which route to take. We know that in doing so we don't get anymore computable function than what we get with nondeterministic TM, but we might get to some answers more quickly.

PAC idea, however, changes things. 1-epsilon is the amount of uncertainty a PAC problem solver can tolerate in calling a solution 'approximately' correct. If epsilon=0, then you get maximal tolerance.

How this idea can be related to Turing's oracle, and to relation between certainty and amount of physical effort.

# Answer
> 1 votes
An oracle access to a random oracle can simulate the effect probabilistic TM's have. However, oracle machines aren't limited to using a random oracle, you can specify whatever oracle you would like, to any problem - no matter how hard the problem is, and a TM with an oracle access to it would solve it in constant time.

So, in this line of thinking - an oracle machine can be thought of as a really general extension of the probabilistic case.

I don't know if this answered your question, but I hope I managed to help a little!

---
Tags: complexity-theory, turing-machines, oracle-machines
---


title: Extended NPDA implementation

text:
# Question
Title: Extended NPDA implementation
In Formal Grammars course we have a task to implement an **extended NPDA** (a pushdown automata where taking any amount of symbols from the stack is allowed (including ε) and it can be in several configurations at the same time) in any programming language. It can be one that accepts with a state or an empty stack.

I have looked around and all implementation algorithms I have found do not allow for transitions like (ε/ε)/A (read nothing, take out of stack nothing, just add A to stack). The problem of course is that there is (as far as I know) no sure way to terminate this kind of branch and, if indeed, input string does not belong to this language, it would just infinitely try to loop and loop these kinds of transitions.

So, my question is - how to implement an extended NPDA? How to know when to stop generating a branch and say "this branch goes nowhere, terminate it"?

Here is an example automata - accepts palindromes.

# Answer
> 2 votes
Take a look at this post.

A general way to remove epsilon transitions is to transform the PDA into a CFG, then take this grammar and convert it back to a PDA. This will result an equivalent PDA that does not need epsilon transitions. Take a look here for the algorithms converting the PDA to CFG and back.

---
Tags: automata, pushdown-automata
---


# Question
Title: Time complexity of $L=\{a^nb^n | n \ge 1\}$
Consider the following language:

$$L=\\{a^nb^n | n \ge 1\\}$$

I constructed the following Turing Machine:

\begin{eqnarray} T &=& (Q, \Sigma, \Gamma, \delta, q\_0, B, F) \nonumber \\ Q &=& \\{q\_0, q\_1, q\_2, q\_3, q\_4\\} \nonumber \\ \Sigma &=& \\{a, b\\} \nonumber \\ \Gamma &=& \\{a, b, X, Y, B\\} \nonumber \\ F &=& \\{q\_4\\} \nonumber \end{eqnarray}

When the input comes as $aabb$, the Turing Machine works like this:

How can you know the time complexity of this Turing Machine?

# Answer
If I correclty understand the algorithm, your TM starts "marking" the first $a$, then it finds the first $b$ and marks it, then it comes back the the first unmarked $a$ and so on. So, assuming that you have in input a string $w$ of lenght $n$ that belongs to the language $L$, you have $\frac{n}{2}$ $a$'s that have to match with the same number of $b$, each $a$ is paired to a $b$ that is $\frac{n}{2}$ cells away, so to perform a complete matching you need $\frac{n}{2}$ transitions from an $a$ to reach the $b$ to be coupled with it, and again $\frac{n}{2}$ transitions to reach the next $a$, so in total $n\cdot \frac{n}{2}$ transitions (actually, you have to perform an extra transition for each letter to put the head in the right place, so the exact amount of transitions is $\frac{n^2}{2}+n+1=O(n^2)$).

Now, let us consider a word $w$ of lenght $n$ that *does not* belong to the language $L$. If it start with $b$, it is immediately rejected, so suppose $w=a^hb^kv$, where $v\in a\Sigma^\*$ has lenght $j\>0$ and $h+k+j=n$. If $k\leq h$, then the TM will performs $\frac{k^2}{2}+k+1$ transitions before stopping (and rejecting $w$), while if $k\>h$, then it will make $\frac{h^2}{2}+h+1$ transitions. So, the worst case correspond to the maximum of the function $$ f(h,k,j)=\cases{\frac{k^2}{2}+k+1, \quad k\leq h\\ \frac{h^2}{2}+h+1,\quad k\> h} $$ on the constraint $h+k+j=n$, $j\>0$, and it is not difficult to see that it is reached for $|h-k|=1$ and $j=1$.

Summing up: the worst case is reached when $w$ belongs to the language $L$, and the TM must carry out $O(|w|^2)$ transitions.

---

If you want to play with your TM and see the exact number of transitions, go here, compile and load a word, enjoy!
> 2 votes

---
Tags: algorithms, turing-machines, time-complexity
---


# Question
Title: Is the union of infinitely many regular languages always regular?
> Prove or disprove or this statement:

> The union of an infinite number of regular languages is regular.

Can someone help?

# Answer
*Every* language is a union of infinitely many regular languages: $$ L = \bigcup\_{w \in L} \\{w\\}. $$
> 3 votes

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


# Question
Title: How can we prove that in binary search, low – high ≤ 1
How can we prove that in binary search

$$\mathit{low} - \mathit{high} ≤ 1$$

Below is a sample algorithm for Binary Search.

```
while (low<=high) {
  int mid = low + (high-low)/2;
  if (data[mid]<value) low = mid+1;
  else if (data[mid]>value) high = mid-1;
  else return &data[mid];
}
return nullptr;

```

A good stranger told me that

> typically you would want to avoid unprotected mid-1 and mid+1 for fear of over- and underflow and have a special case for when the difference between high and low is less than 2.

What I still want to know is a formal proof that $\mathit{low} - \mathit{high} ≤ 1$ provided that you started off with $\mathit{low} ≤ \mathit{high}$.

My idea so far has been to adapt the explanation on loop invariant here but I can assure you I haven't made any progress, yet.

# Answer
Let's denote the indices by $l,h,m$. If $l \leq h$ and $h-l$ is even then $m = \frac{l+h}{2}$ and so in the following iteration, the new values $l',h'$ will either be $\frac{l+h}{2}+1,h$ or $l,\frac{l+h}{2}-1$. In the first case $$ l'-h' = \frac{l-h}{2}+1 \leq 1, $$ and in the second case $$ l'-h' = \frac{l-h}{2}+1 \leq 1. $$

If $l \leq h$ and $h-l$ is odd then $m=\frac{l+h-1}{2}$ and so either $l',h' = \frac{l+h+1}{2},h$ or $l',h' = l,\frac{l+h-3}{2}$. In the first case $$ l' - h' = \frac{l-h+1}{2} \leq \frac{1}{2} $$ and so $l'-h' \leq 0$, since $l'-h'$ is an integer. In the second case $$ l' - h' = \frac{l-h+3}{2} \leq \frac{3}{2}, $$ and so $l'-h' \leq 1$, since $l'-h'$ is an integer.

Put together, we have shown:

> If $l \leq h$ then $l'-h' \leq 1$.

Now let's use it to show that $l-h \leq 1$ always holds.

We first prove by induction on $t$ that if the loop executes at least $t$ times, then after $t$ iterations of the loop, $l-h \leq 1$. The base case $t = 0$ is by assumption. Now suppose that after $t$ iterations, we have $l-h \leq 1$. If $l \> h$ then the loop terminates, and so there is nothing to prove. Otherwise, $l \leq h$, and so $l-h \leq 1$ at the end of the iteration, as shown above.

This shows that when the loop terminates (*if* it terminates — which has to be shown separately), $l-h \leq 1$ necessarily holds. In fact, we can say more: since the loop terminated, we must have $l \> h$, and so $l-h = 1$.
> 2 votes

---
Tags: algorithms, binary-search
---


# Question
Title: Maximum matching using linear programming
In a bipartite graph $G = (V,E)$, there is a neat algorithm for finding a maximum matching (or even a maximum-weight matching) using linear programming. It is explained here. The first step is to solve the following LP:

$$ \text{maximize}~~\sum\_{e\in E} w\_e x\_e \\ \text{subject to}~~\sum\_{e\in E: v\in e}x\_e=1\text{ for all }v\in V \\ 0\le x\_{e}\le 1\text{ for }e\in E. $$

If some value $x\_e$ in the optimal solution is fractional, then there must be another fractional $x\_{e'}$ near the same vertex (since the sum of all edges near each vertex is 1). By following these fractional edges, we eventually find a cycle of fractional edges. We can then move value along the edges in the cycle until at least one edge becomes integral (0 or 1).

A crucial aspect in this solution is that all such cycles are of even length, since the graph is bipartite. If the graph is not bipartite, then the above scheme does not work since we might have odd-length cycles.

QUESTION: Is there a similar algorithm for finding a maximum-cardinality matching, even in unweighted graphs, based on rounding a fractional solution to the above LP?

(I know that this problem can be solved by the blossom algorithm, but it is very complicated and I am hoping that the LP approach can yield a simpler algorithm).

# Answer
> 4 votes
This approach is described by Grötschel, Lovász and Schrijver in their paper The ellipsoid method and its consequences in combinatorial optimization, as well as in their book Geometric algorithms and combinatorial optimization. Edmonds gave a description of the general matching polytope, which has exponentially many defining linear inequalities. While the simplex method cannot be used to optimize the corresponding linear program, other approaches, such as the ellipsoid algorithm and some interior point methods, can use a separation oracle for efficient optimization (at least theoretically).

There is a third algorithm, due to Micali and V. Vazirani, which is however also quite complicated; see the recent exposition by Vazirani.

# Answer
> 2 votes
You can start by modeling the LP problem as in the bipartite case. Then you optimize.

* If the solution found has fractional values, then, there is an odd cycle with fractional values in the subgraph induced by the solution, and **you have to add the corresponding "blossom inequality constraint" to your LP model** "to break" the odd cycle.
* Then you optimize again the augmented LP model.

By repeating this steps, eventually, you will arrive to an integer solution corresponding to a matching.

Here there is a video showing an example: https://youtu.be/lLb52UobMh0

---
Tags: graphs, linear-programming, matching
---


# Question
Title: How does a compiler give an immediate compilation error?
I am confused. I know that compilers translate your code one time as a whole into intermediary code, but how come when I type in something improper, the IDE shoots out a compilation error immediately? What am I not understanding? I thought the whole difference between an interpreter and a compiler is that the former translates code line by line and the latter translates your source program as a whole in one go.

# Answer
> 6 votes
I'll talk about relatively simple (for the sake of analysis) languages, like C#/Java. There may be different approaches aside from want I describe here.

**What IDE does during analysis is not compilation**

The primary goal of IDE is not compilation, it's to assist you with code writing/analysis. For example, IDE helps you with auto-completion, refactorings (renames, indentation, dead code removal, simplifying the code), navigation (go to definition, find usages), code generation (overriding `equals()/hashCode()`, creating constructors, properties generation), and many, many other tasks. On the other hand, it doesn't care about resulting code efficiency, linking, and other compilation-related stuff, but e.g. it cares about preserving comments and spaces (compilers can simply throw them away). It means that IDE can (and will) use completely different structures to work with.

**Code analysis**

The code analysis can usually be split into three steps, in this order (for C++ these steps are mixed, which makes it a hard language):

* Lexical analysis: the input is split into a sequence of tokens. E.g. `a + b` becomes `[IDENT(a), PLUS, IDENT(b)]`.
* Syntax analysis (or parsing; they are not exactly the same, but doesn't matter now): builds a syntax tree. E.g. `a + b` can be parsed as `PlusExpr(left=IDENT(a), PLUS, right=IDENT(b))`. `c = a + b;` can be parsed as `AssignmentStatement(left=IDENT(c), EQ, right=PlusExpr(...), SEMICOLON)`.
* Semantic analysis. Surely a huge field, with a lot of tasks, but for now let's only care about name resolution (finding declarations) and type checking.

**Error detection**

Errors types detected by IDE correspond to code analysis steps outlined above.

* Lexical errors: e.g. you use some invalid token (e.g. `0gda`) or you didn't close a string literal (e.g. `"abc<EOF>`). Usually, lexical analysis is lightning fast, and such errors are trivial to detect. To continue lexical analysis (to detect more errors and allow syntax analysis), bad literals can be ignored or fixed (e.g. the analysis can treat `"abc` as `"abc"`).
* Syntax errors: e.g. you forgot a semicolon `c = a+b<EOF>`, closing parenthesis `c = (a+b;`, etc. Detecting the errors is simple. A tricky part is to recover from the errors. E.g. in `c = (a+b;` you can assume that there should be `)` before `;`, report error, and continue parsing. Anyway, while error recovering is nontrivial (and often requires manual handling), it's usually performed reasonably well.
* Semantic errors. I'll talk about errors like "Undefined identifier" and "wrong type" next.

**Name/Type errors**

In Java, there are no identifiers that come from nowhere (this is one of the reasons why Java is a relatively simple language for analysis). The sources are (as I recall):

* `import` statements.
* Identifiers declared in the same scope. E.g. when you define `class A` at the top level of the file, this class can be used anywhere in the file; when you write `for (int i; ...`, `i` can be used in the body of the loop.
* With qualifiers. E.g. if you have an object `a`, which has a method `b`, you can write `a.b`.

These lead to the following structures:

* For `import` statements, you have a global structure that analyses all source files and all linked libraries. This structure is a trie which represents a global name hierarchy. So if you've written `import java.util.*`, it follows the path `<root>->java->util` and includes all identifiers in the found node into the current file scope.
* For scopes. Consider an example:

```
class A {
    int f() {
        if () {
            print(a);
        }
    }
}

```

In this example, when we try to resolve `a`, we try to find a declaration (in this order): 1) inside `if`-block, 2) inside `f()`, 3) inside `class A`, 4) in the file scope (i.e. because of `import`s). When the name is found, the search is done.

Therefore, for scopes, it suffices to maintain a stack-like structure: each level of the stack represents a scope and has all the names defined in this scope. When trying to find a declaration, you process the stack layer-by-layer.
* For qualifiers: for `a.b`, when resolving `b`, you assume that you've already resolved `a` (using the above rules). Moreover, you assume that you know the type of `a`; it means that the above structures should maintain the types of all identifiers (which is easy to do by looking at the type at the declaration; this is another aspect that makes Java simple). Now, you simply check whether the type has a member `b` and which type it has.

With the above analysis, the type analysis is simple: for each identifier you know its type, and you know which type you expect: e.g. in `f(x,y)`, if you know (after resolution) that `f` is a function `(int, int) -> int`, you know that `x` and `y` should have type `int`.

**Why it can be done fast**

All these structures can be maintained on-the-fly. In the hierarchy trie, the only modified nodes are the nodes corresponding to the current file. The scope stack and access with qualified correspond only to the current file (so you simply need to re-analyze the file). Also, some optimizations may be used to re-analyze only a portion of the file (e.g., if you make edits inside some function, there is a chance that you need to re-analyse only this function).

Actually, the slowest operations are the following:

* Building the hierarchy when the project is first opened.
* Loading the hierarchy when the project is reopened. This is indeed an issue, and a lot of efforts may be required to make this efficient.
* Rebuilding the hierarchy when a lot of files change simultaneously (e.g. because of `git pull`).

**Solution-wide analysis**

I was talking about finding errors in the current file. However, editing the current file may break something else: e.g. if you remove a method from a class, all files using this method will break (the above structures can't detect it unless you open the affected file). This requires a Solution-wide analysis, which, well, analyses your entire project in real-time. This analysis requires much more resources though (at the very least, you need to track all usages of all identifiers, and I believe there is a lot of other stuff going on there), not every machine can handle it on a large project, and it may take some time (few seconds, as I recall) for errors to be detected.

---
Tags: compilers, interpreters
---


# Question
Title: Proof that the length of the largest ascending subsequence is the number of decreasing subsequences
Given a sequence of numbers, I have to prove that the number of decreasing subsequences (non-strictly), so that every number is included in one subsequence and the number of subsequences is minimum is actually the length of one of the longest increasing subsequences. I need to this because I have to prove the greedy algorithm for finding all the decreasing subsequences having as few subsequences as possible. I have no idea of where to start, any help is much appreciated.

Edit: The big, greedy problem sounds like this: decompose the sequence in a minimum number of decreasing subsequences (non-strictly). **Those are the subsequences I am talking about.**

Thank you.

# Answer
You should read up on Patience Sorting first; that's a greedy algorithm to calculate a partition into nonincreasing subsequences (described there as piles of cards). Moreover, the number of subsequences (piles) is minimal.

To prove that, we need to consider two things.

**Claim 1:** the length of the LIS is a lower bound on the number of piles. That follows from the fact that each of the elements in the LIS must go into a different pile, for if any two elements end up in the same pile, it would no longer be nonincreasing.

**Claim 2:** the number of piles obtained by Patience Sorting is a lower bound on the length of the LIS. Wikipedia has a proof. To summarize: whenever we place a card C in pile X \> 1, we add a pointer from card C to the current top card at pile X - 1 (which is necessarily smaller). If we end up with N piles, we can start at the card on top of pile N, and follow back pointers to construct a strictly increasing subsequence of length N (in reverse).

Combine 1 and 2 to conclude that the length of the LIS is equal to the minimum number of nondecreasing subsequences in the partition (and such a partition is produced by Patience Sorting).

If this is still unclear, there is a similar question about Patience Sort here: How to prove the optimality of the "patience sort" algorithm?
> 3 votes

---
Tags: correctness-proof, greedy-algorithms, subsequences
---


# Question
Title: Trouble with Big-O notation proof by definition
> Let $a,b\>0$. Prove $\left(\log\left(n\right)\right)^{a}=O\left(n^{b}\right)$.

I'm supposed to find an algorithm to find the log(n) largest elements in an array and return them sorted and explain why it's bounded by $O(n^{b})$, but the thing is I'm having trouble proving the above and I'm kind of stuck.. Any tips?

# Answer
> 1 votes
As $a$ is fixed, then you can omit it from requirements because for $a \gt 0$ inequality $(\log n)^a \leqslant C n^b$ is equivalent $\log n \leqslant C^{\frac{1}{a}}n^{\frac{b}{a}}$. Denoting $0 \lt \frac{b}{a}=\alpha $ we obtain, that it's enough to proof $\log n \in O(n^\alpha)$ for $\alpha \gt 0$.

To simplify, we can consider $\log n$ with base $e$, because the difference with the other base will be constant factor.

So, last step will be $$\lim\limits\_{n \to \infty}\frac{\ln n}{n^\alpha} = \lim\limits\_{n \to \infty}\frac{1}{\alpha n^\alpha}=0$$

We see, that a more strong result with $o$-little is fair: $\forall \alpha \gt 0$ we have $\log n \in o(n^\alpha) \subset O(n^\alpha)$.

# Answer
> 0 votes
Try using the limit definitions for big-O, and try using Lhopital's rule

---
Tags: algorithms, big-o-notation, upper-bound
---


# Question
Title: Prove that the following language is not a regular language
**Prove that the following language is not a regular language:**

$L = \\{ 0^x1^y | x, y \geq 1\text{ and } x \geq y\vee (x \< y \wedge y \mod x = 0)\\}$

Is there anyone to prove this ?

# Answer
> 2 votes
Assume towards contradiction that the language is regular. Let a be the "pumping length" given by the pumping lemma. Let $p \geq a+2$ be a prime number. Consider the word: $w=0^p1^p \in L$. By the pumping lemma, it can be written as $w=xyz$ where $|y| \geq 1$, $|xy| \leq a $, $xy^nz \in L \ \ ,\forall n \geq 0$. Consider $w' = xy^0z$.

Note that the length of zeros in w' is strictly less than p, and that the length of ones in w' is still exactly p. Also note that the length of zeros in w' is at least 2 since $z$ itself contains at least two copies of zero. Therefore, the number of zeros in w' is $ 1 \< k \< p $. But in order to be in $L$, $w'$ has to satisfy $p \ \ mod \ \ k = 0$, which is equivalent to $k | p$ \- contradiction!

---
Tags: formal-languages, automata
---


# Question
Title: Find all vertices that are included in a simple cycle through a fixed vertex in a directed graph
Given a directed graph $G = (V, E)$ and a vertex $v \in V$, how to find all vertices $v'$ such that exists a simple cycle $v \to ... \to v' \to ... \to v$? That is, to find the set of vertices $$V' = \\{v' : \exists c, \text{c is a simple cycle in G}, v \in c, v' \in c \\}$$

I found this question related: Find all cycles through a given vertex. I can first find all cycles and then union them to get $V'$. However, is there a more efficient way to do so?

# Answer
I believe the problem is NP-hard, by reduction from the two disjoint paths problem.

The two disjoint paths problem is as follows:

> Given a directed graph $G$ and $(s\_1,t\_1),(s\_2,t\_2)$, find two paths $s\_1 \leadsto t\_1$ and $s\_2 \leadsto t\_2$ that are vertex-disjoint (they have no vertex in common).

This problem is NP-hard.

We can reduce two disjoint paths to your problem. In particular, given $G$ and $(s\_1,t\_1),(s\_2,t\_2)$, we construct a new graph $G'$ by adding new vertices $v,v'$ and adding edges $v \to s\_1$, $t\_1 \to v'$, $v' \to s\_2$, $t\_2 \to v$.

Notice that any pair of vertex-disjoint paths $s\_1 \leadsto t\_1$, $s\_2 \leadsto t\_2$ will yield a simple cycle

$$v \to s\_1 \leadsto t\_1 \to v' \to s\_2 \leadsto t\_2 \to v.$$

Also, within any simple cycle $v \leadsto v' \leadsto v$ we can find simple paths $s\_1 \leadsto t\_1$, $s\_2 \leadsto t\_2$ that are vertex-disjoint. It follows that there exists a simple cycle $v \leadsto v' \leadsto v$ in $G'$ iff there exist two vertex-disjoint paths $s\_1 \leadsto t\_1$, $s\_2 \leadsto t\_2$ in $G$. So, any algorithm for solving your problem would immediately yield an algorithm for solving the two disjoint paths problem.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: Sorting criteria for Kruskal's algorithm
I am studying Kruskal's algorithm. Is the only acceptable sorting criteria to sort edges from lowest weighted edge to greatest weighted edge? I ask this because I assume that if the algorithm used an alternative sorting criteria say, greatest to lowest, then it would not produce a MST. My reasoning is that edges with larger weights would be added first.

Any help with this concept would be greatly appreciated.

# Answer
Yes, for Kruskal's you have to sort it in ascending order of weights, for precisely the reason that you gave.

There is, however, another algorithm, namely Reverse-Delete which is essentially the opposite of Kruskal's. You start with the original graph, and process edges in descending order of weight. Then we remove each edge while the graph is still connected.
> 2 votes

---
Tags: algorithms, graphs, weighted-graphs, minimum-spanning-tree
---


# Question
Title: Determine whether a sorted array contain at least 4 distinct elements in O(log n) time
On one of my previous courseworks, I was faced with the following problem, which I think is unrealistic when using a direct / straightforward approach that usually algorithms have by leveraging certain data structures like dictionaries, etc.

> Design an O(log n) algorithm whose input is a sorted list A. The algorithm should return true if A contains at least 4 distinct elements. Otherwise the algorithm should return false.

My lecturer came up with the following solution:

```
def ThreeDiff(A):
  if A[0]==A[len(A)-1]:
    return -1

  minind=0
  maxind=len(A)-1

  while maxind-mind>1:
    midind=int((minind+maxind)/2)
    if A[midind]>A[minind] and A[midind]<A[maxind]:
      return midind
    if A[midind]==A[minind]:
      minind=midind
    else:
     maxind=midind
  return -1

def FourDiff(A):
  midind=ThreeDiff(A)
  if midind==-1:
    return false
  return ThreeDiff(A[0:midind+1])!=- 1 or ThreeDiff(A[midind:len(A)]) != -1

```

Is there a cleaner or better way to solve this problem?

# Answer
Here is a cleaner and better way to solve the problem.

```
# Return the smallest index where the element is bigger than `A[start_index]`.
# If `len(A)` is returned, no element is bigger than `A[start_index]`.
def next_bigger_element(start_index, A):
    lo, hi = start_index, len(A)
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if A[mid] == A[start_index]:
            lo = mid
        else:
            hi = mid
    return hi

def distinct_elements_at_least(k, A):
    if len(A) == 0:
        return k <= 0
    index = 0
    count = 1
    # keep finding the next bigger element until `k` elements have
    # been found or we have reached the end of the array.
    while count < k and A[index] != A[-1]:
        index = next_bigger_element(index, A)
        count += 1
    return count >= k

```

To find whether `A` contains at least 4 distinct elements, just call `distinct_elements_at_least(4, A)`.

This program works correctly for any given number `k`. For example, it can be used to check whether `A` has 0 element or whether `A` has 7 distinct elements. For any fixed `k`, it works in $O(\log n)$ time as at most `k` binary searches on an interval of size at most `n` are done.

---

If you do not mind `import bisect`, you may prefer the following shorter code, since method `next_bigger_element` is no longer needed.

```
from bisect import bisect_right

def distinct_elements_at_least(k, A):
    if len(A) == 0:
        return k <= 0
    index = 0
    count = 0
    while index < len(A) and count < k:
        count += 1
        index = bisect_right(A, A[index], index + 1)
    return count >= k

```
> 2 votes

---
Tags: algorithms, binary-search
---


# Question
Title: Given an algorithm, is it possible to find all other equivalent algorithms for the same computable function in the same model
For any computable-function, there may be multiple different algorithms (possibly countably infinite). For example, sort has many different implementations/algorithms, that we know of or that we have found so far. They all produce the same output for the same input.

Given any specific computable-function or even a specific instance of an algorithm/implementation (for any model of computation, functional in lambda calculus, imperative in turing machines, or any other) for it, is it possible to enumerate/find all other equivalent algorithms/implementations for that same computable-function, for the same model.

ie. If I have an algorithm or even a specification for sort, it is possible to find the other algorithms for sort?

# Answer
Interpreting your problem as finding a computable $f$ such that $f\big(\langle M\rangle\big)=\langle M'\rangle$ with the property that $M'$ enumerates all programs equivalent to $M$, i.e. all $M''$ with $L(M'')=L(M)$, the answer is no (such $f$ does not exist).

One way to show this is to observe that such $f$ would place the language $\left\\{\big(\langle M\_1\rangle, \langle M\_2\rangle\big) \big| \\; L(M\_1)=L(M\_2)\right\\}$ in $RE$, while it is known that this language is $\Pi\_2$ complete and thus not in $RE$. You could formulate this relative to any admissible numbering, and not necessarily in the language of Turing machines.
> 2 votes

# Answer
You should think in Turing Machines.

If I understand correctly, what you ask is more or less "Given the code of a Turing Machine, is it possible to enumerate the codes of all Turing Machines with the same language?".

I think this is not possible, because it is undecidable to know whether two TM have the same languages (all the more so list all TM with the same language).
> 1 votes

---
Tags: algorithms, complexity-theory, undecidability, type-theory, computation-models
---


title: Analysing time complexity

text:
# Question
Title: Analysing time complexity
Okay so we've been given an algorithm and asked to give an upper bound to its best and worst case

```
weirdSort(A,r,p)

if r < p

q = (r+p)/2
BubbleSort(A,r,q)
wierdSort(A,q+1,p)
Merge(A,r,q,p)

```

I'm not quiet sure how to do that.. this is my first time analysing time complexity and I'm quiet lost

I know that an upper bound for BubbleSort is $O(n^{2})$ for worst and $O(n)$ for best, and for Merge is $O(n)$ for both (Merge being the function that merges the arrays in MergeSort)

So for the worst case I have

$T\left(n\right)=T\left(\frac{n}{2}\right)+O\left(n^{2}\right)+O\left(n\right)\ ➜\ T\left(n\right)\ =\ T\left(\frac{n}{2}\right)+c\_{1}n^{2}+c\_{2}n$

and for the best case

$T\left(n\right)=T\left(\frac{n}{2}\right)+2O\left(n\right)\ ➜\ T\left(n\right)\ =\ T\left(\frac{n}{2}\right)+c\_{1}n$

But now what? how do I handle $T\left(\frac{n}{2}\right)$? What are the steps I need to take in these types of questions? I feel like they've just thrown us in the water without really explaining how to solve stuff..

# Answer
> 1 votes
Try to find an explicit formula for $T(n)$: Start by writing a few examples, such as $T(2)$, $T(4)$, etc.

Then, after you got some intuition on how $T(n)$ behaves, formulate it as a summation, and find a closed form for it. I will give the example of how to do it for the "best case" scenario:

## Examples

$T(2) = T(1) + c\_1 \cdot 2$

$T(4) = T(2) + c\_1 \cdot 4 = T(1) + c\_1 \cdot 4 + c\_1 \cdot 2 = T(1) + c\_1 \cdot (4 + 2)$

$T(8) = T(4) + c\_1 \cdot 8 = T(1) + c\_1 \cdot 8 + c\_1 \cdot 4 + c\_1 \cdot 2 = T(1) + c\_1 \cdot (8+4+2)$

## Opening recursion

And now (try for yourself) you can prove using induction that:

$T(n) = T(1) + c\_1 \sum\_{k=1}^{\lfloor \log(n)\rfloor} \frac{n}{2^k}$

## Finding closed form

Notice that $\sum\_{k=1}^{\lfloor \log(n)\rfloor} \frac{1}{2^k} = \frac{\left(\frac{1}{2}\right)^{\lfloor \log(n) \rfloor} - 1}{\frac{1}{2}-1} = \frac{1 - \frac{1}{n}}{\frac{1}{2}} \le 2$ Since it is the sum of a geometric progression.

Therefore, $T(n) = T(1) + c\_1 \cdot n \cdot \sum\_{k=1}^{\lfloor \log(n)\rfloor} \frac{1}{2^k} \le T(1) + c\_1 \cdot 2 \cdot n = O(n)$

# Answer
> 1 votes
I think you've already done most of the work. Now it's just solving the recurrences $$T(n)=T(\frac{n}{2})+O(n)$$ and $$T(n)=T(\frac{n}{2})+O(n^2)$$ Both are pretty straightforward. The key is to keep substituting until you find a pattern, after which you analyze what will happen when the recursion bottoms out. There are 2 common methods, namely the recursion tree method, and the substitution method. The former is more diagrammatic, while the latter involves more algebra.

Here is a great video that solves your first recurrence (best case) while explaining both methods in detail.

Your second recurrence (worst case) has solutions here

For more insight, here are some great lecture notes on solving recurrences.

---
Tags: algorithms, time-complexity, upper-bound
---


# Question
Title: How can I prove the following problem is NP complete?
## The problem:

I have a list $\displaystyle S=\\{s\_{1} ,s\_{2} ,\dotsc ,s\_{n}\\}$ places. Each unordered pair of places has cost and gain: $\displaystyle c\\{s\_{i} ,s\_{j}\\} \in \mathbb{N}$, $\displaystyle g\\{s\_{i} ,s\_{j}\\} \in \mathbb{N}$. Also the pairs are only for $\displaystyle i\neq j$.

I have two numbers: $ $$\displaystyle b\in \mathbb{N}$, $\displaystyle p\in \mathbb{N}$.

The problem is to check wether it exist a combination of pairs such that:

$\displaystyle c\_{1} +c\_{2} +\dotsc +c\_{m} \leqslant b$ and $\displaystyle g\_{1} +g\_{2} +\dotsc +g\_{m} \geqslant p$. Where of course $\displaystyle c\_{i} ,g\_{i}$ are cost and gain of a used pair $s\_i$.

To show it is NP-complete I have to show a Karp reduction.

---

There are some problems we've studies and so that I can use:

Clique, Composite, SAT - Satisfiability problem, 3SAT, CSAT, IS - Independent Set, VC - Vertex, Cover, DHC - Directed Hamilton Cycle, HC - Hamilton Cycle, DS - Dominating Set, SSS - Subset, Set, 3COL, Partition, Bin-Packing.

Since it's talking about a sum I thought of using Subset-sum. If I set $\displaystyle p=b=k$, and I set $\displaystyle c\_{i} =g\_{i}$ for each $\displaystyle i$, then it really is just a sum question, to find a combination of elements of sum $\displaystyle k$.

But what it's complicating it for me is that if I have $\displaystyle n$ elements, I will have $\displaystyle \frac{n^{2} -n}{2}$ pairs, and so these many different costs. How can I rewrite the $\displaystyle n$ elements of partition, into some $\displaystyle k$ elements here such that there are $\displaystyle \frac{k^{2} -k}{2} =n$ pairs?

I've thought maybe I can only assign the cost to the first $\displaystyle n$ elements, and then all the rest to $\displaystyle 0$, but then cost and gain must be natural numbers.

Any advice?

# Answer
> 2 votes
I think there is an easy reduction from Knapsack.

> Knapsack:
>
> * Input: a list of couples (value, weight) $\\{(v\_1, w\_1), …, (v\_n,w\_n)\\}$, a maximum weight $W$, a target value $V$
> * Question: is there a subset $S \subset \[\\!\[1, n\]\\!\]$ such that $\sum\limits\_{i\in S} v\_i \geq V$ and $\sum\limits\_{i\in S} w\_i \leq W$

Now given an input of knapsack, let's construct an input of your problem: add a $n+1$-th element, and consider:

* $\forall (i, j) \in \[\\!\[1, n\]\\!\]$ with $i\neq j$, we set $c\\{i, j\\} = \infty$ and $c\\{i, n+1\\} = w\_i$
* $\forall (i, j) \in \[\\!\[1, n\]\\!\]$ with $i\neq j$, we set $g\\{i, j\\} = 0$ and $g\\{i, n+1\\} = v\_i$
* set $b = W$ and $p = V$

Then this instance has a solution of your problem if and only if the input of knapsack has a solution. Since knapsack is $NP$-complete, this proves the $NP$-hardness of your problem.

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


# Question
Title: Closure of regularity under the action of replacing identical pairs of letters
Given any regular language L, we define $$shrink(L) = \\{ \sigma\_{1}\sigma\_{2}\sigma\_{3}...\sigma\_{n} : \sigma\_{1}\sigma\_{1}\sigma\_{2}\sigma\_{2}\sigma\_{3}\sigma\_{3}...\sigma\_{n}\sigma\_{n} \in L \\} $$

The question is whether these languages are regular or not.

The intuition says they are, and I was thinking about proving it with Homomorphism, i.e defining homomorphism from shrink(L) by duplicating each word and then proving that $h(shrink(L))$ is regular therefore shrink(L) is regular.

But I'm not exactly sure how to do it properly..

edit: another idea I had is by using DFA - if L is regular it has a DFA called M, so I can build M' by changing Delta such that $\delta (q,\sigma w) = \delta(\delta(q,\sigma w),\sigma w)$. Will it work?

Thanks for any help

# Answer
> 2 votes
You can do it using homeomorphism. Define $h:\Sigma\rightarrow \Sigma^\*$ by: $h(\sigma)=\sigma\sigma$.

Then, $h$ induces a homeomorphism $g$ that is defined by $g(\sigma\_1,\dots,\sigma\_n)=h(\sigma\_1)\dots h(\sigma\_n)$.

Then, its easy to see that $shrink(L)=g^{-1}(L)$ (prove this!). From closure properties of regular languages we know that $g^{-1}(L)$ is regular, hence also $shrink(L)$.

---
Tags: regular-languages
---