# Question
Title: How get the permutation of two lists but the elements of each list remain in the same order?
So if I have `lst1 = [a, b]` and `lst2 = [x, y]` the result would be:

```
[x, y, a, b]
[x, a, y, b]
[x, a, b, y]
[a, x, y, b]
[a, x, b, y]
[a, b, x, y]

```

I'm thinking about doing something recursive where I take the first element of a list, place it at the start, then recursively take the next element of that list and shift it through each position (and on each shift go through all remaining elements of that list).

But I'm wondering if there may be a nicer way to do this?

edit: Some more elaborate info here

# Answer
> 3 votes
Generate a string `chi` with `len(lst1)` 0s and `len(lst2)` 1s, e.g. for `lst1 = [x, y]` and `lst2 = [a, b, c]`, you generate `chi = [0, 0, 1, 1, 1]`. Then you **shuffle** `chi` to obtain your *"characteristic vector"*. This new list will dictate the order in which to output elements from `lst1` and `lst2`.

I hope this Python program speaks for itself:

```
from random import shuffle

def permutation(lst1, lst2, chi):
    idx1 = 0
    idx2 = 0
    for i in range(len(lst1) + len(lst2)):
        if chi[i] == '0':
            yield lst1[idx1]
            idx1 += 1
        else:
            yield lst2[idx2]
            idx2 += 1

lst1 = 'xy'
lst2 = 'abc'

chi = list('0' * len(lst1) + '1' * len(lst2))
shuffle(chi)
print(''.join(chi))
print(''.join(list(permutation(lst1, lst2, chi))))

```

Outputs:

```
11001
abxyc

10011
axybc

00111
xyabc

```

---
Tags: algorithms
---


# Question
Title: How can a quadratic algorithm be faster than a linearithmic one?
I have to solve the following problem:

> Al and Bob are arguing about their algorithms. Al claims his $O(n\log n)$ time method is always faster than Bob’s $O(n^2)$ time method. To settle the issue, they perform a set of experiments. To Al’s dismay, they find that if $n\<100$, the $O(n^2)$ time algorithm runs faster, and only when $n \geq 100$ is the $O(n\log n)$ time one better. Explain how this is possible.

Watching the Big O definition I can see that $f(x)$ is $O(g(x))$ if there are constants $C$ and $k$ such that $|f(x)|\leq C|g(x)|$ whenever $x\>k$. Also, I know that $O(n^2)$ comes from a polynomial of degree 2 that might have a coefficient and other terms of lower degree.

I do not find how to relate this facts in order to make a conclusion although I suspect that constants $C$ and $k$ could play an important role in such a conclusion.

I will very much appreciate any clue so I can get a better idea about how to formulate an answer.

# Answer
> 7 votes
All you know is that an $O(n\log n)$ algorithm is eventually (a lot) faster than an $O(n^2)$ algorithm, but for any specific value of $n$, you can't say anything. Indeed, the asymptotic growth of the function doesn't depend on its value on $n \< 100$. This means that if $f(n) = O(n^2)$ then for all $c\_1,\ldots,c\_{99}$, the following function is also $O(n^2)$: $$ f'(n) = \begin{cases} c\_n & \text{if } n \< 100, \\ f(n) & \text{if } n \geq 100. \end{cases} $$ So asymptotic notation is completely uninformative regarding the performance of algorithms on specific values of $n$.

You could say that functions such as $f'(n)$ are artificial and never really occur in practice. This is not quite true (you can hard-code some auxiliary information for small $n$, for example), but even if you consider "natural" functions, asymptotic notation doesn't help you to determine anything other than asymptotics: consider for example $n^2$ against $10^{100} n\log n$ (such examples definitely happen in practice, for example in fast matrix multiplication).

# Answer
> 6 votes
Remember, that all asymptotic analysis tells us is how the running time varies with the size of the input *for a particular algorithm*. It doesn't tell us how many seconds it will take for an implementation of the algorithm to complete with a given input size. But we do know that if an O(n2)) algorithm takes X seconds to process a set of items, it will take approximately 100 times as long to process 10 times as many items.

Asymptotic notation eliminates constant factors because they're not really relevant to how the running time grows with the size of input. When you're talking about using an O(n2) algorithm on 1,000,000 items, it's unlikely that your constant factor is going to make much difference; the `n^2` term is going to dwarf it.

You can, however, estimate the constant factors. One way is by counting "basic operations" to come up with a rough estimate of how much work is done per iteration. Or, you could run both algorithms with some sample input, count the iterations, and figure out how many microseconds it takes per iteration. Either way, you'll come up with a value that is the constant for that particular algorithm.

So, say you want to compare insertion sort (an O(n2) algorithm with Quick sort (O(n log n)). We know from empirical evidence that insertion sort is faster than Quick sort when n is small (how small is another question). That's why optimized Quick sort implementations switch to insertion sort when the subarray is less than 10 or so items.

Using one of the techniques I described above, you determine the constants for each of the algorithms. Let's call them Ci and Cq. Given that, we can *estimate* that insertion sort will be faster than Quick sort when (Ci * n2) \< (Cq\*(n log n)).

It should be obvious from looking at the two algorithms that Ci \< Cq. The insertion sort is incredibly simple. The algorithm is nothing but comparison and swap, with a little loop overhead thrown in.

Quicksort is a little bit more complex, requiring more steps per iteration, but fewer iterations.

Consider sorting a five element array. Insertion sort will do, at worst:

* 5 increments and comparisons of the outer loop control variable
* 15 increments and comparisons of the inner loop control variable
* 15 element comparisons
* 15 swaps

Now look at Quicksort, which in the *average* case has to partition four subarrays. The 5-element array gets split into two subarrays of 3 and 2 elements. The 3-element subarray is further partitioned into subarrays of 1 and 2 elements. And then the two 2-element subarrays are partitioned.

So the `partition` method will be called four times. Each partition step requires a minimum of two swaps in addition to the comparison and swapping of elements, and other overhead. When you add it all up, you see that Quicksort does more work per iteration. When the number of iterations is small, Insertion sort does less total work even though it does more iterations.

# Answer
> 4 votes
the question and answers have a lot of notation. how about a picture, "worth a lot of words" and some zen-like visual/ geometric intuition? this is a simple graph of $x \log(x)$ (red) vs $x^2/15$ (green). rest of explanation (of the graph vs big O notation, etc) left as exercise to reader (eg also solve for exact region where one is supposedly "faster" than another etc, and reformulate the functions slightly so that it matches the constants $C,k$ in the question, etc).

# Answer
> 0 votes
Solving $c\ n^2 = k\ n \log(n)$ for n, gives us a "point of no return" - value of `n` from where going upwards into n domain $O(n\log n)$ always wins : $n\_{critical} = e^{-W(-c\ / \ k)}$.
`W` is Lambert W function ( or so called *product logarithm* ).

BTW it's worth to say that if $k \< e\ c$, then there is no intersection point between those two curve types (no solution) , thus in this case small values of `n` where $O(n^2)$ wins - **doesn't exist**

So in general - region of `n` where $O(n^2)$ wins, depends on constants $c,k$. And these are directly related to operations amount/cost in loops of both type of algorithms. Bigger values of c,k indicates that some loop operations costs *more* for a CPU. Thus theoretically fast algorithm can be amortized by heavy operations for CPU.

---
Tags: algorithms, landau-notation, efficiency
---


# Question
Title: Is a particular string regular (e.g is '010') regular?
If the alphabet is $\\{0,1\\}$, then is the string '010' regular?

I think it is regular because DFA and regular languages are equivalent and this string has a DFA but at the same time it seems to contradict pumping lemma which implies not regular. Here is what I mean.

For pumping lemma first we have to take $w$ only in the language (here the language is just '010') So $w=$ '010'. I choose $k = 2$ then the new string $w=xy^kz$ has length more than 3 so it is definitely not '010', which means this language is not regular!

What am I missing?

# Answer
Being regular is a property of *languages*, not of *words*.

However, it seems that by '010' you really mean the language consisting only of the single word '010', that is, $\\{ 010 \\}$. This language, just like any other finite language, is regular.

Where does your pumping lemma proof fail, then? Here is a complete statement of the pumping lemma.

> If $L$ is a regular language then there exists a constant $n$ such that for all words $w \in L$ of length at least $n$ there is a decomposition $w = xyz$, where $|xy| \leq n$ and $y \neq \epsilon$, such that $xy^iz \in L$ for all $i \geq 0$.

Your argument is ignoring the constant $n$, which could be larger than the length of all words in $L$.
> 11 votes

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


# Question
Title: Floyd Warshall's All pair shortest path problem does not evaluate all possible paths
We know that the FW all pair shortest path is a Dynamic Programming (DP) approach to solving the problem. Being a DP, it smartly evaluates **all** possible options before deciding the final option at each stage.

I have manually evaluated and traced a 5 node graph with this algorithm. The actual graph is not important here. I will take the example of the evaluation of path(V4,V5) in iteration 1 and 2 only:

**Stage 1**: min{(4,5),(4,1,5)} of Stage 0

**Stage 2**: min{(4,5), (4,2,5)} of Stage 1

So if we expand this, then by the end of Stage 2, we have actually essentially evaluated the paths {(4,5) , (4,1,5), (4,2,5), (4,2,1,5), (4,1,2,1,5)} and selected the minimum.

As seen, we are evaluating cyclic paths as well e.g. (4,**1,2,1**,5) from above. If we continue tracing the algorithm till the end, we find that we never evaluate the path (4,2,1,2,5) for this specific example. Does this mean, not all paths are evaluated with this algorithm? I know not evaluating it won't harm as it will definitely not be the shortest path but my point is that should have been the case with (4,1,2,1,5) too. It looks like although the output is correct and consistent, yet theoretically speaking certain paths are not evaluated because of the way the algorithm is structured and not out of merit. Am I missing something here?

# Answer
> 1 votes
Yes, the path $(4,2,1,2,5)$ is not evaluated. However this is not a problem.

Since we assume that the graph doesn't contain any negative cycles (this is a requirement for FW), there exists an optimal path for each pair of nodes that doesn't contain any cycles. Therefore the algorithm only needs to guarantee, that cycle-less path gets evaluated.

By induction you can show that this is always the case. Let $k$ be the variable in the most outer loop. Induction hypothesis: After the $k$th iteration the table contains all the shortest paths between each pair that only uses nodes $\le k$ on the path (without start and end node).

At the beginning this is trivially true. And also the induction step, going from $k$ to $k+1$, is pretty easy to show: A minimal path using only nodes $\le k + 1$ from $u$ to $v$ either contains only nodes $\le k$, or it contains a minimal path from $u$ to $k+1$ combined with the minimal path from $k+1$ to $v$. (Here we use the fact that the paths contain no cycles. If a path contains cycles, this statement ca be wrong.) And exactly this case is handled in the algorithms.

Therefore at the end the table contains all minimal paths.

# Answer
> 1 votes
> Being a DP, it smartly evaluates **all** possible options before deciding the final option at each stage.

I think this is a misrepresentation of what DP means. Dynamic programming is basically divide-and-conquer with memoisation. For problems whose solutions have the right structure it guarantees to find the optimal solution, but it doesn't guarantee to evaluate the entire solution space: a DP algorithm can freely discard parts of the solution space which are demonstrably incapable of contributing to an optimal solution.

---
Tags: algorithms, graphs, dynamic-programming, weighted-graphs
---


# Question
Title: Max number of configurations of a Turing Machine
I was wondering about a result in the Sipser book which states that any $f(n)$ space bounded Turing machine also runs in time $2^{O(f(n))}$.

Is this because a configuration consists of a state, a position of the head and the contents of the work tape, which is $\vert Q \vert \cdot f(n) \cdot \vert \Gamma \vert ^{f(n)}$. To be honest I'm not quite sure why this is equal to $2^{O(f(n))}$. Wouldn't this only be the case when your work tape alphabet consists of 2 symbols?

Probably a silly question, but thanks anyway.

Also, I did not quite understand if this result changes when we consider logspace bound Turing machines.

# Answer
Yes, that's right. If there are $k$ possible configurations, then any such Turing machine either runs in time at most $k$, or it loops forever. That's because if it runs for at least $k+1$ time steps, some configuration must be repeated; and if a configuration is repeated, it will continue repeating forever.

Let $|\Gamma|=2^c$, i.e., $c = \lg |\Gamma|$. Then $|\Gamma|^{f(n)} = (2^c)^{f(n)} = 2^{c f(n)} = 2^{O(f(n)}$. For similar reasons, $\vert Q \vert \cdot f(n) \cdot \vert \Gamma \vert ^{f(n)} = 2^{O(f(n)}$. So, the number of possible configurations of a $f(n)$-space-bounded Turing machine is $2^{O(f(n)}$, and thus any such machine must either halt in time at most $2^{O(f(n)}$ or loop forever.
> 6 votes

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


# Question
Title: Why " every non-prime attribute of R is non-transitively dependent on every key of R" in the original def of 3NF?
I have read the definition in of Third\_normal\_form here , which shows

> The third normal form (3NF) is a normal form used in database normalization. 3NF was originally defined by E.F. Codd in 1971.\[2\] Codd's definition states that a table is in 3NF if and only if both of the following conditions hold:
>
> > 1. The relation R (table) is in second normal form (2NF)
> > 2. Every non-prime attribute of R is non-transitively dependent on every key of R.

From the book Database Systems The Complete Book 2nd Edition, key means candidate key.

And I got the definition of transitive dependent here. So my problem is this: From the quoted definition, if we denote any non-prime attr as $x$, any key of $R$ as $K$, suppose $x$ is subset of an attributes group $A$, we can easily construct some $A$ satisfied $$K \rightarrow A \wedge A \nrightarrow K \wedge A\rightarrow x $$ so where am I wrong?

# Answer
In `K→A`, the `K` and `A` stand for sets of attributes. Let's suppose `K` is `{j, k}` and `A` is `{x, y, z}`. Then we have

```
{j, k} → {x, y, z}

```

Then `x` is dependent on the key, and that dependency is non-transitive.

`A` (i.e. `{x, y, z}`) is not a key for `R` (we're supposing), so the fact that `{x, y, z}` trivially Functionally Determines `{x}` (search for 'trivial' here) does not fall under the 2nd bullet that you quote from wikipedia on 3NF.

You might prefer to work with the Zaniolo 1982 definition that wikipedia gives. Because this is self-contained/doesn't need cross-referring to 2NF. (It'll also help you see the difference to BCNF, sometimes called "~~two~~three-and-a-half Normal Form".)

Be careful to observe that given some set of FDs for a relation, you can derive further FDs, including the trivial FDs. (See Armstrong's Axioms and 'Closure' on the FD's article.) Then the fact that you can derive some dependency transitively which is the same as a non-transitive dependency already given, is just a tautology.

**Addit:** in response to comments "transitive dependent ... I still need some authoritative expression"

Ok. Looking at the wikipedia definition of 'Transitive Dependency' you have linked to in the q:

> A transitive dependency can occur only in a relation that has three or more attributes. Let A, B, and C designate three distinct attributes (or distinct collections of attributes) in the relation.

Your formula mentioning `K, A, x` is not "three ... distinct collections of attributes": specifically `x` is not distinct from `A`; `x` is an element of `A`. Therefore your `K → A ∧ A /→ K ∧ A → x` does not represent a transitive dependency. But we do have that `K→x`. Therefore `x`'s dependency on `K` must be non-transitive.

So in wikipedia's definition of 3NF, its definition of transitive dependency is sloppy.

To put it in sharp focus: imagine your `K` contains only a single attribute `k`; imagine your `A` contains only a single attribute `x`. Now you can't apply the definition of transitive dependency: `R` contains less than 3 attributes.
> 0 votes

---
Tags: database-theory, databases, normal-forms, relational-algebra
---


# Question
Title: How does one use the Nerode-Myhill theorem to prove that a language is regular?
Showing that a language is not regular is straight-forward, because all one needs to do is find an infinite set of inputs which has an injective mapping to the set of equivalence classes which compose that language.

How does one show that the set of equivalence classes of $L$ is finite? For instance, how would one show that the simple language $L = \\{s: |s| \equiv 0 \mod 2\\}$ has a finite number of equivalence classes?

I think that showing that there is a surjective mapping is not sufficient, because the image may still be of infinite size.

# Answer
It is just as straightforward to show a language is regular using Nerod-Myhill theorem as to show a language is not regular using that theorem since Nerode-Myhill theorem characterizes when a language is a regular.

For example, let us take the simple language $L=\\{s: |s|\equiv 0 \text{ (mod 2)}\\}$. There are two equivalent classes of $L$, assuming $a$ is a letter in the alphabet.

* $\left\[\epsilon\right\]\_{\equiv\_{L}}=\left\\{s: |s|\equiv 0\text{ (mod 2)}\right\\}$
* $\left\[a\right\]\_{\equiv\_{L}}=\left\\{s: |s|\equiv 1\text{ (mod 2)}\right\\}$

It should be easy for you to show that the above two classes are well-defined equivalence classes of $L$. There are no other equivalence class of $L$, since every word belongs to one of two classes. If a word is of even length, it belongs to class $\left\[\epsilon\right\]\_{\equiv\_{L}}$; otherwise, it belongs to class $\left\[a\right\]\_{\equiv\_{L}}$.

Hence, there are two equivalence classes of $L$ in total. That is, the number of equivalence classes of $L$ is finite. According to the Nerode-Myhill theorem, $L$ must be regular.

> I think that showing that there is a surjective mapping is not sufficient, because the image may still be of infinite size.

I am not sure which surjective mapping you are talking about.

As you can see from the example above, it is enough to show that the union of the finitely many equivalence classes you have found contains all words. Why? If we have another equivalence class $E,$ let $w\in E$. Then $w$ must belong to $F$, one of the equivalence classes you have found. Since $E$ and $F$ share one word, they are the same equivalence class. That is, $E$ has been found.

You may want to check a few related questions and answers such as *finding separating words (Nerode)* and *how I can find all equivalence classes by Myhill-Nerode?*.
> 5 votes

---
Tags: complexity-theory, computability, regular-languages
---


# Question
Title: The idea behind the state of Imperative languages
I was reading about programming paradigms and I have a question about the state when speaking about Imperative languages. What does it mean to change the program's state? Is it just an abstract idea? I know that `C` is in the Imperative paradigm (In fact in the Procedural paradigm), so it has a state, but I don't understand how it is expressed in language. Is there a special space in memory that contain `1` or `0`? But then, what `0` and `1` represent?

If for example we have:

```
int x = 5;
printf("%d,5);

```

How the state will be affected by each line? Also, why Functional languages does not have one and what is the impact of having one.

As you can see, I'm a bit confused about the idea behind the state. I think that a small example make a bit clear.

I also read the previous thread from the second site, but it didn't help me to understand.

# Answer
> 10 votes
The simplest kind of state is the configuration of memory. In C this memory is accessed through variables (and arrays and pointers, but let us ignore those), so the state is the values of variables.

For example, suppose we have variables `x` and `y` whose values are `23` and `42` respectively (and no other variables). Then we could write the state as $$\[x \mapsto 23, y \mapsto 42\]$$ If we run the program

```
x = 1 + y

```

the state will change to $\[x \mapsto 43, y \mapsto 42\]$. When we declare a local variable, the state will be *extended* temporarily with that variable.

There are many other kinds of state, such as:

* in an object-oriented language each object has its own state, namely the values of its attributes
* a finite state automaton has states, obviously

In general, there is going to be a set $S$ of all possible states. For instance, 1 GB of memory corresponds to $S$ with $2^{2^{30}}$ elements because that's how many states there are for 1 GB of memory. A program which uses state and computes a value of type $A$ can then be thought of as a function $S \to A \times S$: it takes the initial state $s \in S$ and returns a pair $(a, s')$ where $a$ is the computed value and $s'$ the final state.

It is *not* true that functional languages have no state! The *pure* functional languages such as Haskell and do not have built-in state, but other functional languages do have state. For instance OCaml and SML both have references, which are just mutable memory locations, so they have state. Racket and Scheme have state as well, and they are functional languages.

Perhaps a clarification is in order: a language is *functional* if functions are values, which means that we can do with functions whatever we can do with other values (pass them around, make arrays of functions, etc.). For some reason people often confuse *pure* and *functional* languages.

**Supplemental:** Since we're on the brink of a religious war about "Does C++/Java/whatever have first-class functions?", let me throw the first grenade. For a language to be *functional* the following have to be possible:

1. Read an integer `n` from standard input and create a list or an array of functions $\[f\_1, \ldots, f\_n\]$ where $f\_i(x) = x + i$. This disqualifies C.
2. Allow function abstractions in the sense that it is possible to create a function based on a function rule, written as $\lambda x . E$, or $x \mapsto E$, or `lambda x: E`. Very importantly, there must be no scoping limitations on the abstraction, which means that $E$ may *refer to any variables that are in scope*. This disqualifies Java and C++.

There are fundamental mathematical reasons why function abstraction must be unrestricted. With restricted function abstraction we just don't get what is mathematically called a "function". We get something else, but not functions.

# Answer
> 1 votes
The state of a program is all the information that is needed at runtime to determine what each line does.

Consider a simple example that needs no state:

```
printf("%d", 1 + 1);

```

What is the effect of this line? Obviously it prints the number 2. But what about this example:

```
printf("%d", x + 1);

```

Now it's not so clear what this line does. The number printed to the screen depends on the value of `x`. Thus the value of `x` is part of the state of the program. The result of executing that line of code varies depending on the value of `x`. If `x` was a value loaded in from a file the user specified, then the result of this `printf` may not even be knowable at compile time. It may only be known at runtime!

Programming languages pay attention to this concept because it is an essential aspect of optimization. Consider this silly piece of code:

```
int a = y * 42;
int b = y * 42;
int c = y * 42;
int d = y * 42;
int e = y * 42;
...

```

It would be nice to just calculate `y * 42` once and re-use the value. But that's not *technically* what is written. The code written says we need to do the multiplication each time. However, if we can show that `y` does not change between the first and last line (that portion of the program's state doesn't change), then we can optimize all those extra multiplications away.

Pure functional languages take this to an extreme. An expression in a pure functional language is stateless -- it always evaluates to the same thing. They do all sorts of clever tricks to make this happen. These tricks seem rather absurd (Reading about Haskell's monads for the first time should always be accompanied by a stiff drink). But the reward for all these tricks is that the functional programming languages can do some remarkably clever optimizations that are *incredibly* difficult to do in a language which requires one to pay attention to state.

Why have state? Why not just go all pure-functional? Well, sometimes the absurdity of those tricks starts to add up, and it can get increasingly hard to figure out what is actually going on because you, as the developer, are responsible for tracking all sorts of details. Meanwhile, with imperative languages like C, it is easier to write these things. (Pure-functional programmers will argue that it's not easier, but the modern development community at large has substantially chosen stateful languages because people find them easier).

And nowdays, with the powerful optimizers that are available, it is often possible to write in an imperative language, with state, and have the optimizer analyze your code and prove that certain segments of the code are stateless and optimize them as such. Optimizers get better every year, so they're now pretty good at figuring these sorts of things out.

---
Tags: programming-languages, programming-paradigms, imperative-programming
---


# Question
Title: How can I create a language using set operation to prove a language is not regular?
My goal is to show, that a given language is not a regular one by using the Properties of Regular Languages.

The language is $ A \triangleq\left\\{w \in \Sigma^{\*} \mid |\left.w\right|\_{b} \neq|w|\_{c} \wedge|w|\>0\right\\} $ with $ \Sigma \triangleq\\{a, b, c\\} $

My idea is to use this clearly non regular language (which is given in the task, so I can/should use it) $ \left\\{b^{n} c^{n} | n \in \mathbb{N}\right\\} $ to prove $A$ is also no regular language.

Could the following work?

$(A\cap L(b^\*c^\*)) \cdot \mathrm{L}(\boldsymbol{\epsilon}) = \left\\{b^{n} c^{n} | n \in \mathbb{N}\right\\}$

# Answer
It looks like you are onto the right track. However, your notation is confusing me.

I would believe the following is what you are coming at.

$$\overline{(A\cap L(b^\*c^\*))} \cup \\{\epsilon\\} = \left\\{b^{n} c^{n} \mid n \in \mathbb{N}\right\\}$$ where $\overline S$ is the language of words not in $S$, a.k.a. the complement of $S$. Here are the facts that you will use.

* $b^\*c^\*$ is a regular expression.
* the intersection of two regular languages is regular.
* the complement of a regular language is regular.
* $\\{\epsilon\\}$ is a regular language.
* the union of two regular languages is regular.
* $\\{b^{n} c^{n} \mid n \in \mathbb{N}\\}$ is not regular.

I will leave the rest of reasoning to you.
> 1 votes

---
Tags: regular-languages
---


# Question
Title: Does a binary code with length 6, size 32 and distance 2 exist?
The problem is to prove or disprove the existence of $C$, s.t., $|c| = 6,\forall c\in C$; $|C| = 32$; $d(c\_i,c\_j)\geq2,1\leq i\<j\leq32$. ($d$ stands for hamming distance)

I tried to construct a satisfying code. The best I can get is to let $C = C'\times C'$, a concatenation of $C' = \\{000,011,110,101\\}$, which is of size 16. 32 happens to be the theoretical upper bound of the size, now I don't know what to do next so as to solve the problem.

# Answer
Yes, there is such a set. You are actually on the right track to find the following example.

Let $C = \\{c : |c|=6 \text{ and there are even number of 1's in c}\\}$. You can check the following.

* $|C|=32$.
* $d(u,v)\geq2$ for all $u,v\in C$, $u\not=v$. (In fact, $d(u,v)=2$ or 4 or 6.)

---

Here are four related exercise, listed in the order of increasing difficulty. As in the question, only binary code is concerned.

**Exercise 1.** Give another example of a set of 32 words of length 6 and pairwise distance at least 2.

**Exercise 2.** Show that there are only two such sets, as given in the answer and in the exercise 1.

**Exercise 3.** Generalize the above to words of any given length and pairwise distance at least 2. (Hint, $32=2^{6-1}$.)

**Exercise 4.** (further generalization stated in Yuval's answer) If $A(n,d)$ is the maximum size of a code of length $n$ and minimum pairwise distance $d$, then $A(d,2d)=A(n-1,2d-1)$.
> 9 votes

# Answer
All words of even parity from a linear code with $2^{n-1}$ codewords and minimum distance $2$.

More generally, if $A\_2(n,d)$ is the maximum size of a code of length $n$ and minimum distance $d$, then $A\_2(n,2d) = A\_2(n-1,2d-1)$.
> 7 votes

---
Tags: information-theory, coding-theory, encoding-scheme
---


# Question
Title: What is a flow through the cut in the Ford-Fulkerson algorithm?
In page 12 of the slide, it states flow across a cut $(S, T)$ is $f(S, T) = \sum\_{u\in S} \sum\_{v\in T} f(u,v) - \sum\_{u\in S} \sum\_{v\in T} f(v,u)$.

I think the first part $\sum\_{u\in S} \sum\_{v\in T} f(u,v)$ is the amount of flow entering the network at the source node. The second part $\sum\_{u\in S} \sum\_{v\in T} f(v,u)$ is the amount of flow leaving the network at the sink node. Shouldn't these two be the same? Why the flow across a cut is the difference of these two?

# Answer
> 2 votes
Consider a graph of two node $s$ and $t$ and one edge $(s,t)$ with a flow $f$, $f(s,t)=1$.

Let $S=\\{s\\}$ and $T=\\{t\\}$. Then the flow across the cut $(S, T)$ is, apparently 1. Or, $$f(S, T) = \sum\_{u\in S} \sum\_{v\in T} f(u,v) - \sum\_{u\in S} \sum\_{v\in T} f(v,u)= f(u,v)=1.$$

$\sum\_{u\in S} \sum\_{v\in T} f(u,v)$ is the flow from $S$ to $T$. $\sum\_{u\in S} \sum\_{v\in T}f(v,u)$ is the flow from $T$ to $S$. Their difference is the flow across $(S,T)$.

Note that all ideas above does not depend on which is source node nor which is sink node. The flow across a cut $(S,T)$ just means how much (water, current, resource, etc) is flowing from $S$ to $T$.

---

It happens that it is required the source node is in $S$ and the sink node is in $T$ in that part of the proof. That requirement does NOT affect the explanation above. It is just a convenience measure since in a flow network we are only interested in that kind of cut. However, it does make the situation somewhat confusing.

Now let $s$ be the source node and $t$ be sink node. So that the cut $(S,T)$ above is indeed a cut as required in the proof.

> the first part $\sum\_{u\in S} \sum\_{v\in T} f(u,v)$ is the amount of flow entering the network at the source node. The second part $\sum\_{u\in S} \sum\_{v\in T} f(v,u)$ is the amount of flow leaving the network at the sink node. Shouldn't these two be the same? Why the flow across a cut is the difference of these two?

The first part $\sum\_{u\in S} \sum\_{v\in T} f(u,v)=f(u,v)$ is not necessarily the amount of flow entering the network at the source node, although it happens to be in the current example.

The second part $\sum\_{u\in S} \sum\_{v\in T} f(v,u)=0$ is not necessarily the amount of flow leaving the network at the sink node. In fact, it is not in the current example! The amount of flow leaving the network at the sink node is
$\sum\_{u\in V}f(u,t)=1$. Now, can you read the following again?

The second part $\sum\_{u\in S} \sum\_{v\in T} f(v,u)$ is the flow from $T$ to $S$ while $\sum\_{u\in V}f(u,\text{the sink node})$ is the flow from all nodes to the sink node. Even if $T$ consists of the sink node only, these two sums are different. The former is for flow **from the sink node** and the latter is for flow **to the sink node**. They are not only different. They are very different! They are too different.

---

Here are a few easy exercises about a general flow network $G=(V,E)$ with source node $s$ and sink node $t$ and a flow $f$.

**Exercise 1.** The amount of flow entering the network at the source node is the flow across the cut $(\\{s\\}, V\setminus\\{s\\})$.

**Exercise 2.** The amount of flow leaving the network at the sink node is the flow across the cut $(V\setminus\\{t\\}, \\{t\\})$.

**Exercise 3.** The amount of flow across any cut is the same.

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


title: Chess pieces placement algorithm

text:
# Question
Title: Chess pieces placement algorithm
I've got the following problem:

* I've got chessboard with fixed size **N x M**
* I've got list of pieces, like 2 queens, 2 rooks (It can be any piece with exception of pawn).
* I need to find every combination where none of the pieces is in a position to take any of the others

For example for chessboard **3 x 3** and **2 rooks** and **1 king**, possible solutions are:

```
 |R|        |R|      K| |      | |K
-+-+-      -+-+-     -+-+-    -+-+-
R| |        | |R      | |R    R| |
-+-+-      -+-+-     -+-+-    -+-+-
 | |K      K| |       |R|      |R|

```

What I came out with:

1. I create a whitelist of fields where the new piece can be placed (at the beginning it has all fields of the chessboard)
2. I take the first piece from the list
3. I place it on the first field I take from whitelist: **(1,1)**
4. I update whitelist excluding all fields that are threatened with this piece I placed
5. Here I branch out: I take next piece from the list and call my method recursively on every field from the whitelist (I also need to check, if placing new piece would threat already standing piece).
6. I repeat it until the last piece is placed
7. If there are pieces left, but no fields on whitelist I just finish that branch.

I noticed I can calculate results only for first quadrant (fields **(1,1),(1,2)(2,1),(2,2)** for my example. Rest of the solutions can be received by just mirroring results from the first quadrant.

Problem with my solution is, it's not very fast. For chessboard **7x7** and 7 pieces it takes ~15 minutes to finish. I implemented it with scala.

Do you have any tips about how can I improve it?

# Answer
Suppose you're trying to place $Q$ queens, $R$ rooks, $B$ bishops, $N$ knights, and $K$ kings. Then doing things the way you're doing them now, at least provided the language isn't clever enough to memoize the pure function calls for you, means that you're processing each solution $Q!R!B!N!K!$ times, rather than once, since in a solution containing $Q$ queens you could have placed them in any of $Q!$ different orders, and so forth.

Similar logic also applies to the partial solutions in your call stack.

If you're just trying to place one of each piece then this isn't so bad. If, on the other hand, you're trying to place 8 queens on an 8 x 8 board, this means each solution gets generated 8! = 40,320 different times.

This is probably the single largest issue you're seeing here. I tested this out by writing a naive python program, and it was able to do 8 queens on an 8x8 board in considerably less than fifteen minutes running on a single core of my twelve-year-old laptop with 1GB of RAM.

I'm not particularly familiar with Scala but it's possible you could just keep your existing code but tell it to memoize your function, at least provided it's written as a pure function.

Other optimizations would be to parallelize the analysis (which, again, a functional language like Scala might be able to do near-automatically for you), and to take advantage of the four- or eightfold-symmetry of the problem (depending on whether the board is square or just rectangular) by putting everything into a canonical form.

One last thing to check is that the intermediate data is stored in such a way that you're not having to recalculate anything. When checking for a blank square, you want a stored list of blank squares you can iterate over. When checking to see if the piece you just added is threatening something already on the board, you want a stored list of occupied positions to work with.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Graph partitioning with parts of equal size
> Partition an undirected graph of $n$ nodes into $k$ subgraphs so that total vertices inside all subgraphs is maximum.
>
> Restriction: all subgraphs have the same number of nodes (so $k$ divides $n$); $k$ is given initially.

I'd like to receive pointers to the solution as well as papers or blogs related to or expanding on it.

# Answer
> 2 votes
Your problem is a special case of graph partitioning. When $k=2$, the problem is known as *minimum bisection*, and is NP-complete.

---
Tags: algorithms, graphs
---


title: Find path from node

text:
# Question
Title: Find path from node
I have a question where I need to find a path from node 1 to node N in an undirected graph given weights in `O(A Log^2 A)`.

The total cost of each path must not exceed *`T`* amount of total weight.

For no1, you cannot use this path because its total cost is `more than` 13.
For no2 and no3, you only can use no2 because the `maximum weight(7)` of no2 is smaller than the `maximum weight(8)` of no3. So I am expected to print out `7` as a final answer.

I understand that this problem is quite similar to the Widest Path Problem

But the problem here cannot use `Prims` or `Kruskal` because the route chosen might not include the path that is expected.

The current solution I have would be to use DFS and find all the possible paths and attempt to compare the weights. I have no idea how would I complete within the `O(A Log^2 A)`.

# Answer
> 1 votes
Dijkstra's algorithm allows you to determine the shortest path from 1 to $N$ is time $O(E\log E)$. In particular, by considering only edges of weight at most $w$, you can check whether there exists a path of length at most $T$ in which the maximum weight edge is at most $w$.

You can now use binary search to find the optimal value of $w$. After spending $O(E\log E)$ time to sort the edge weights, the binary search involves $O(\log E)$ invocations of Dijkstra's algorithm, for a total running time of $O(E\log^2 E)$.

---
Tags: java
---


# Question
Title: Calculating the number of assignments satisfying a general propositional formula
I know, for a disjunctive clause of the form $x\_1 \vee ... \vee x\_i$, the number of assignments satisfying it is simply $2^i - 1$, but what about for a general formula? Is the number of satisfying assignments be calculated polynomially?

In Papadimitriou's Computational Complexity (p. 301), when explaining an approximation algorithm for $k$-MAXGSAT where the input is, over $n$ variables, $\Phi = \\{\phi\_1, ..., \phi\_n\\}$ with $\phi\_i$ being any general formula involving at most $k$ variables, it is stated that

> ... Each expression $\phi\_i \in \Phi$ involves $k$ Boolean variables. Out of the $2^k$ truth assignments, we can easily calculate the number $t\_i$ of truth assignments that satisfy $\phi\_i$. ...

But I don't find it obvious how one can compute it easily, as even with Tseitin's method, the transformed result of $\phi\_i$ wouldn't necessarily be a single disjunctive clause. Where did I go wrong?

# Answer
> 4 votes
As I have mentioned in the comments, being able to determine the number of truth assignments of a generic formula in polynomial time would imply not only $\textbf{P} = \textbf{NP}$ but actually the much, much stronger $\textbf{#P} = \textbf{P}$ (see Yuval Filmus' answer).

What Papadimitriou *really* means in this context is that the number of truth assignments of each $\phi\_i$ depends on the value of only $k$ variables, with $k$ *being constant with respect to $n$*. Thus, determining the number of truth assignments can be done in constant time (relative to $n$, not to $k$; for a more precise runtime bound, see again Yuval Filmus' answer).

For reference, here is the earlier paragraph from the text (emphasis mine):

> In this problem we are given a set of Boolean expressions $\Phi = \\{ \phi\_1 , ... , \phi\_m \\}$ in $n$ variables, where each \[...\] is a general Boolean expression involving at most $k$ of the $n$ Boolean variables, where $k \> 0$ is a **fixed constant** \[...\]

# Answer
> 3 votes
Counting the number of satisfying assignments in known as #SAT, and is the canonical #P-complete problem. In particular, we don't expect it to be possible to count the number of satisfying assignments of a $k$-variable formula of size $m$ in much better than $O(2^km)$. In contrast, an $O(2^km)$ algorithm does exist – just try all possible assignments.

---
Tags: time-complexity, satisfiability, polynomial-time
---


# Question
Title: Euclidean algorithm and well define ness on the underlying set
Euclidean algorithm is given below:

> gcd($a$,$b$):
>
> if $a=0$, return $b$
>
> otherwise, return gcd($b \bmod a$, $a$)

Let us first argue that the algorithm terminates. The reason is that each time the number is decreasing, and there is a well-ordering defined on the set from which number $a$ and $b$ are defined.

**Question:** What if the well-ordering is not defined on the set from which elements $a$ and $b$ are coming? In that case can we say that algorithm will take finite time? To me it appears no, but the reasoning is not clear to me.

# Answer
We can think of the GCD algorithm as taking place inside a directed graph. The vertices of the graph are all pairs $(a,b)$, where $a,b \geq 0$. If $a \neq 0$, then there is an edge from $(a,b)$ to $(b \bmod a, a)$. The algorithm starts at some vertex $(a,b)$, follows the unique outgoing edges, until (hopefully) reaching a leaf $(0,b)$, at which point it outputs $b$.

We can consider a more general situation, in which we are given a directed graph in which every vertex has at most one outgoing edge, and a starting vertex. We start at that vertex, and follow the unique outgoing edges, stopping if we ever reach a leaf. In this generality, we cannot be certain that the process always terminates. In fact, if the graph contains a directed cycle and we start with a vertex on the cycle, the process will ever terminate!

Consider for example the graph on $1,2,3$ with edges $1\to 2$, $2 \to 3$, $3 \to 1$. On this graph, the iterative process will never terminate.

There is another reason for the process to not terminate: there might be an infinite directed path. For example, consider the directed graph on the integers in which the edges are $a \to a+1$. This graph contains no cycles, but nevertheless the process does not terminate.

To show that the GCD algorithm always terminates, we define a potential function $\phi$ on the vertices by $\phi(a,b) = a$. If $(a,b) \to (b \bmod a,a)$ then $$ \phi(b \bmod a,a) = b \bmod a \< a = \phi(a,b). $$ Therefore the potential decreases. Since the potential is always a natural number, and these are well-ordered, it cannot decrease forever, and therefore the algorithm necessarily terminates.

To finish, let me mention the Collatz conjecture. Consider the directed graph on the positive integers in which the edges are $2n \to n$ and $2n+1 \to 3n+2$ for all $n \geq 1$. The Collatz conjecture states that the process considered above always terminates, no matter what the starting vertex is. The conjecture is suspected to be true, but nobody knows how to prove it.
> 0 votes

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


# Question
Title: Connected components of the graph on $[n]$ in which $i,j$ are connected if $\mathrm{gcd}(i,j) > g$
I recently got asked the following question:

> A set of $n$ cities are numbered from 1 to $n$. Given a positive integer $g$, two cities are connected if their greatest common divisor is greater than $g$. The number $n$ may be as large as $10^5$.
>
> Alice has a list of $q$ cities that she'd like to visit. Given Alice's list of $q$ origin cities and $q$ destination cities, return a boolean vector with a 1 in the $i$th position indicating that it's possible to reach the $i$th destination city from the $i$th origin city, and 0 if not. The length of the list $q$ may be as large as $10^5$ as well.

I solved this problem with a quadratic time solution. However, the large upper bound for $n$ and $q$ clearly implies there is a better runtime. I haven't yet seen a way to speed up the creation of the graph, however.

My solution builds the graph in quadratic time, using a union find data structure to handle the component merging, and Euclid's algorithm for computing gcd's.

The fundamental question is whether there exists a faster than $O(n^2)$ algorithm to construct and query an undirected graph, when edges are defined by a pairwise rule, and it appears that every pair $(i, j)$ for $1 \leq i,j \leq n$ needs to be looked at.

# Answer
> 4 votes
Given parameters $n$ and $g$, you want to find the connected components of the graph on $\[n\] := \\{1,\ldots,n\\}$ whose edges are $\\{(i,j) \in \[n\] : (i,j) \> g\\}$. Let us write these edges in a different way: $$ \bigcup\_{d=g+1}^n \\{(i,j) \in \[n\]: d \mid (i,j) \\} = \bigcup\_{d=g+1}^n \\{(dI,dJ) : 1 \leq I,J \leq n/d \\}. $$ For each $d$, we have a clique on $\lfloor n/d \rfloor$ vertices. We can preserve the same connectivity properties by replacing it with a path: $$ \bigcup\_{d=g+1}^n \\{(dI,d(I+1)) : 1 \leq I \< \lfloor n/d \rfloor \\}. $$ The number of edges in the new graph is $$ \sum\_{d=g+1}^n \lfloor n/d \rfloor \leq n \sum\_{d=g+1}^n \frac{1}{d} = O(n\log n). $$ You can find the connected components using BFS/DFS in time $O(n\log n)$, a large improvement over your quadratic time algorithm.

# Answer
> 1 votes
Pseudo code for finding the minimum connected edges.

```
    n=100
    lst = range(1,101)
    g=10
    ans = list(tuple())
    for d in range(g+1,n+1):
       for i in range(1,n/d):
         ans.append((d*i,d*(i+1)))
    print ans
    print "size="+str(len(ans))

```

Output:

```
   [(11, 22), (22, 33), (33, 44), (44, 55), (55, 66), (66, 77), (77, 88), (88, 99), (12, 24), (24, 36), (36, 48), (48, 60), (60, 72), (72, 84), (84, 96), (13, 26), (26, 39), (39, 52), (52, 65), (65, 78), (78, 91), (14, 28), (28, 42), (42, 56), (56, 70), (70, 84), (84, 98), (15, 30), (30, 45), (45, 60), (60, 75), (75, 90), (16, 32), (32, 48), (48, 64), (64, 80), (80, 96), (17, 34), (34, 51), (51, 68), (68, 85), (18, 36), (36, 54), (54, 72), (72, 90), (19, 38), (38, 57), (57, 76), (76, 95), (20, 40), (40, 60), (60, 80), (80, 100), (21, 42), (42, 63), (63, 84), (22, 44), (44, 66), (66, 88), (23, 46), (46, 69), (69, 92), (24, 48), (48, 72), (72, 96), (25, 50), (50, 75), (75, 100), (26, 52), (52, 78), (27, 54), (54, 81), (28, 56), (56, 84), (29, 58), (58, 87), (30, 60), (60, 90), (31, 62), (62, 93), (32, 64), (64, 96), (33, 66), (66, 99), (34, 68), (35, 70), (36, 72), (37, 74), (38, 76), (39, 78), (40, 80), (41, 82), (42, 84), (43, 86), (44, 88), (45, 90), (46, 92), (47, 94), (48, 96), (49, 98), (50, 100)]
   size=101

```

We can see that edges like (11,33), (11, 44) etc are not part of the set even though they are directly connected.

After we get the minimum number of connected edges we can apply disjoints sets to solve the above question.

# Answer
> 0 votes
Hint: to determine whether there is a path from source $s$ to destination $t$, factor both $s$ and $t$. What properties need to hold true about their factorization, for such a path to exist?

---
Tags: algorithms, graphs, connected
---


# Question
Title: Running Dijkstra on particular graph with negative weight
After running Dijkstra on this graph from S, which shortest paths will be incorrect?

This graph has a negative weight, so which shortest paths will be incorrect? after my first attempt I got that Y and Z have wrong shortest paths, but that's not true. Can anyone explain why?

# Answer
The shortest path tree of Dijkstra will set root as $S$ then it first selects the $Y$ with weight 8. Then it will look at the shortest distance of all the neighbor's of the tree. There will be two candidates $X$ and $Z$. It will choose $X$ since the distance is 10. Then finally, it will choose $Z$ with distance 11.

The Dijkstra's, as stated, cannot work correctly on graphs with negative weights.

The problem is that it is a greedy algorithm and once it finds the shortest path for a node it is not re-evaluating for any other possibilities may occur in the future. This is not possible if the graph has not negative weights.
> 1 votes

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


# Question
Title: Merge sort: sorting and merging complexity $\Theta(n)$
So this is the Master theorem for Merge Sort:

$$ T(n) = 2T(n/2) + \Theta(n). $$

I am not able to understand why is the time complexity for sorting and merging $\Theta(n)$.

Is sorting $O(1)$ and merging $O(n)$?

# Answer
> 6 votes
Each iteration of merge sort consist of 2 phases:

1. Merge Sorting the first and the second half separately.
2. Merging the two halves.

So in your equation phase 1 is represented by $2T(n/2)$. This means that merge sort is called on the two halves. This is a recursive call, which is why $T$ is used here.

Phase 2 is represented by $\Theta(n)$. Merging two lists of length $a$ and length $b$ takes $\Theta(a+b)$. In our case the two lists are both of size $\frac{1}{2}n$, so we get a total of $\Theta(n)$.

In the end we get that $T(n) = $ **step 1 + step 2**, resulting in $T(n) = 2T(n/2) + \Theta(n)$

---
Tags: algorithms, time-complexity, master-theorem, mergesort
---


# Question
Title: Why aren't primality tests easily linear in time complexity?
Why don't we consider them as linear? I don't understand. You just have to check for factorization up to sqrt of n. So it's even faster than linear. I assume it's not linear only if we compare the number of operations relative to the input in terms of binary representation. But why would we do so? It seems to me wrong. The growth in calculation should be calculated compared to the number itself. Why do we compare it to the binary representation?

# Answer
It seems that the main sticking point of the question here is: Why express runtime in terms of the size of the input, rather than the numeric value that the input represents? And indeed in some cases it doesn't make much difference which way you choose to express it. For instance, we could say that the time to read all values in an $N\times N$ matrix is quadratic in the number of columns, or we could say it is linear in the number of cells, and the meaning of these is the same, just with different conventions.

So let's look at some reasons why it is conventional to express operations on numbers in terms of the length of the number rather than its numeric value:

* It is more easily comparable to operations on other kinds of data, since every possible form of input has a length but not all forms of input have a numeric value. By consistently using the length of the input as our reference point across a variety of problem types, we also get some nice properties like "the runtime of an algorithm that reads the entire input can never be better than linear."
* It provides more useful time complexities in context. For instance, a common use for primality testing is for cryptography. When we're doing cryptography, we might use say a 512-bit number as a key. We would like to have algorithms that scale proportional to the length of the number (512), rather than its numeric value (about $2^{512}$), since $2^{512}$ is such an astronomically large number that even a "linear" time algorithm would never realistically finish.
* It relates better to the actual operations performed by the computer. Many people are accustomed to implicitly treating all numbers as capped at some fairly large constant like $2^{64}$, and thus all arithmetic operations are constant-time and the actual internal representation of the number is irrelevant. But when we are analyzing the big-O performance of operations on the number itself we cannot assume that numbers are always small enough to ignore their internal representation. Ultimately, these operations are performed on bits so the number of bits is a good reference point to use for describing the performance.

As a thought experiment, try analyzing the performance of the addition operation. You may have always considered it a constant-time operation, but what happens if the numbers in question get arbitrarily large? Ultimately, you'll need to sum each digit one-by-one, carrying as necessary. It makes sense to describe this as a linear-time operation based on the length of the input, rather than logarithmic time based on the numeric value of the input.
> 16 votes

# Answer
Simple. When you give the number *one trillion* as input to your algorithm, do you give it as 1'000'000'000'000, or as a terabyte large string of ones?

And by all means, you are free to choose whichever representation you feel comfortable with.

We analyze the runtime as a function of *the size of the input*, not as *the magnitude of the number represented by the input were the input to be a number*.
> 5 votes

# Answer
There are two sensible ways to define a variable that can be used in the runtime complexity.

1. $m$ is the value of the input number (your definition).
2. $n$ is the number of bits required to represent the input (the input size).

Neither is better than the other, because there's a 1-to-1 correspondence between the two:

* $n = O(\log m)$, or equivalently
* $m = O(2^{n})$

Most scientists use $n$. Using that definition, sorting is e.g. $O(n \log n)$ and there's no known $O(n)$ algorithm for primality. You showed that there is a $O(\sqrt m)$ algorithm (sublinear in $m$), which is $O(\sqrt 2^n)$ (exponential in $n$).

Using the definition of $m$, we're not looking for a (sub)linear algorithm for primality; we're looking for a polylogarithmic algorithm, $O((\log m)^c)$ for some constant $c$.
> 5 votes

# Answer
I just got a couple of students curious on this confusion and I tried answering it as follows. (Different to above responses).

First, note that if we were not concerned about the magnitude of input value but only its n-bit representation then the same would apply to analysing sorting algorithms too. But irrespective of what the input numbers magnitude or bits are sorting is nlgn. Agreed?

So why bother on n-bit when dealing with primality or GCD?

To me (and I can be wrong) this is done so to have a worst case complexity analysis. Notice that this part is where my response is different from above.

So going back to sorting, when we say to analyse an input array of size 10^6 we see different cases. And give our big-oh analysis for the worst case of size 10^6. Stay with me!

If we were to plot the nlgn time complexity on x-y what we will do is that we will take an array of size 1, 2, 3,..., 100, 101,..., 1000, ..., 10^5.... and for each of them find the number of basic operation count.

The size of array goes on x-axis and count of basic operation on y-axis. Right? We don't do that too often but that's how we would do it. This would give us an increasing function. I hope you are still reading.

So now back to primality testing. If I plot the same x-y time complexity function and take magnitude on x-axis and count of steps on y-axis, can you imagine what will happen? (Raise of hands, how many of you have guessed the next part?)

For above plot we get following values:

x | y

2 | 1

3 | 2

4 | 1

5 | 4

...

1000 | 2 (why? its divisible by 2)

So we get a zig-zag shape like efficiency function. That's not right, order of growth were supposed to be monotonically increasing, I mean, they should GROW not SHRINK.

So what's actually needed in this case is that we take the number of digits of number of bits of input as the size of input. Now our analysis is meaningful like the sorting example. Why?

It's because for every n-bit (or n-digit) number we take the worst case from the variety of cases. What we can say is that any even number of size n is a best case for primality and any prime number of size n is its worst case.

So we plot the time complexity as a function of bits of the input and not its magnitude.
> -1 votes

---
Tags: algorithm-analysis, time-complexity, runtime-analysis
---


# Question
Title: Sorting "almost sorted" array in $O(n\log\log n)$
> Given array $A$ of length $n$, we call it *almost sorted* if there are at most $\log n$ indices satisfying $A\[i\] \> A\[i+1\]$.
>
> Find an algorithm that sorts the array in $O(n\log\log n)$.

My attempt:

* Create an array $B$ of size $\log n + 1$.
* Go through the array $A$, recognize the $\log n$ pairs, and insert them into $B$.
* Sort $B$ using insertion sort in time $O(\log^2 n)$.

At this point I am stuck.

# Answer
> 6 votes
Suppose that $A$ is an array with $m$ indices satisfying $A\[i\] \> A\[i+1\]$. You can find these indices in $O(n)$. These $m$ indices split $A$ into $m+1$ nondecreasing arrays $B\_1,\ldots,B\_{m+1}$ of total length $n$. We now merge them according to the following strategy: at each step, take the two shortest arrays, and merge them. You can implement the choice mechanism in $O(m\log m) = O(n\log m)$ using a heap.

When merging two arrays of length $a,b$, the running time is $O(a+b)$. Hence we would like to understand the total sum $S$ of $a+b$, where $(a,b)$ goes over all $m$ pairs of arrays being merged. To this end, we consider a *merge tree*, which is formed in the following way. We start with $m+1$ vertices corresponding to $B\_1,\ldots,B\_{m+1}$. When two arrays corresponding to vertices $x,y$ are merged, we create a new vertex with $x,y$ its only children. You can check that $$ S = \sum\_{i=1}^{m+1} |B\_i| \mathrm{depth}(B\_i). $$ Consider now a probability distribution $X$ on $\[m+1\]$ with $\Pr\[X=i\] = |B\_i|/n$. Then $S/n$ is the average codeword length of an optimal prefix code for $X$ (this is because we're essentially running Huffman's algorithm). Therefore $S/n \< \log m + 1$, showing that the merging steps take $O(n\log m)$ time in total.

Summarizing, the algorithm runs in time $O(n\log m)$.

(Strictly speaking, to handle the cases $m=1$ and $m=0$, we should replace $m$ with $m+2$.)

# Answer
> 3 votes
This is a classical application of natural merge sort as described in this wikipedia entry or this algorithmist entry

What is the current case?

Let $A$ is an array with $m$ indices satisfying $A\[i\] \> A\[i+1\]$. We can find these indices in $O(n)$. These $m$ indices split $A$ into $m+1$ nondecreasing arrays $B\_1,\ldots,B\_{m+1}$ of total length $n$. This is our start of merging processing. (Thanks to Yuval for this initial processing.)

Then we will merge $B\_1$ with $B\_2$ into nondecreasing array $C\_1$, $B\_3$ with $B\_4$ into nondecreasing array $C\_2$, and so on. We might have a single $B\_{m+1}$ as $C\_{m/2+1}$ when $m$ is even. This iteration take $O(n)$ time since merging two arrays of length $a,b$ takes $O(a+b)$ time.

Then we will merge $C\_1$ with $C\_2$ into nondecreasing array $D\_1$, $C\_3$ with $C\_4$ into nondecreasing array $D\_2$, and so on. We might have a single array at the end that is not merged but renamed to $D\_{\text{an appropriate index}}$. This iteration take $O(n)$ time as well.

And so on.

Each iteration take $O(n)$ time. There are $\lceil \log\_2(m)\rceil$ iterations. So the total time-complexity is $O(n\log m)$ for $m\>1$. (The time-complexity is $O(n)$ when we find $m=0, 1$.)

---
Tags: sorting
---


# Question
Title: For sorting 10^9 unique 9-digit numbers, would radix sort or counting sort be faster, and why?
> For sorting $10^9$ unique 9-digit numbers, would radix sort or counting sort be faster, and why?

I know that radix sort is $O(nk)$ and counting sort is $O(n+k)$, but can’t understand how to apply this.

# Answer
We can fill in the numbers for both:

### Radix Sort

The complexity of radix sort is $O(nk)$ with $k$ being the size of the numbers. Therefore we get approximately $9 \cdot 10^9 = 9.000.000.000$ iterations for Radix sort.

### Count Sort

The complexity of radix sort is $O(n+k)$ with $k$ being the range of the numbers. In the worst case the range is $10^{9} -1$. So we get approximately $10^{9}-1 + 10^9 = 2.000.000.000$ iterations for count sort.

So count sort would be faster.
> -2 votes

# Answer
There are exactly 10^9 unique nine digit numbers, so the sorted array is just 0, 1, 2, 3, ..., 999,999,999.
> 1 votes

---
Tags: algorithms, sorting, radix-sort
---


# Question
Title: An approximate quantity of multiplications in $\mathbb{F}_p$ amounting the same bit complexity as one inversion in $\mathbb{F}_p$
Consider a prime finite field $\mathbb{F}\_p$ of quite large characteristics $p$, for example $\log\_2(p) \approx 256$ bits. I would like to know an approximate quantity of multiplications in $\mathbb{F}\_p$ amounting the same bit complexity as one inversion in $\mathbb{F}\_p$. Of course, this depends on many factors, hence I propose to listen your ideas rather than exact results. May be, is there an article or book, which discusses this topic?

# Answer
> 2 votes
The standard algorithm for inverting an element is using the extended Euclidean algorithm. You can read all about this connection on Wikipedia.

# Answer
> 2 votes
One algorithm to compute inverses in a finite field is to raise to a large power. In particular, $x^{-1} = x^{p-2}$ if you are working in $\mathbb{F}\_p$ (by Fermat's little theorem). You can use standard algorithms for fast modular exponentiation to compute this with about $2 \lg p$ multiplications, or fewer (depending on the specific value of $p$ and the length of the shortest addition chain for $p-2$).

Another algorithm is to use the extended Euclidean algorithm, as Yuval Filmus explains. I'd expect this to be faster in most cases.

---
Tags: time-complexity, number-theory, multiplication, modular-arithmetic, computer-algebra
---


title: Solving T(n) = T(n-1)*T(n-2)

text:
# Question
Title: Solving T(n) = T(n-1)*T(n-2)
So, this is how I solved

$\displaystyle T(n-1) \approx{} T(n-2) $

$\displaystyle T(n) = T(n-1)^2 $

Add log in both sides

$\displaystyle log(T(n)) = 2log(T(n-1)) $

$\displaystyle Let\\:\\: log(T(n)) = S(n) $

$\displaystyle S(n) = 2(S(n-1)) $

We know that from Fibonacci series

$\displaystyle S(n) = O(2^n) $

$\displaystyle log(T(n)) = O(2^n) $

$\displaystyle (T(n)) = O(2^{2^n}) $

Ok, so where did I go wrong here??

# Answer
> 2 votes
### What is wrong?

> So, this is how I solved
> $T(n-1) \approx{} T(n-2)$
> $T(n) = T(n-1)^2$

An equality is the most precise and most powerful entity in the world. Please treat it with due respect.

Let me show how wrong it is if you use approximation liberally with equalities. If your argument above is sound, we can also do the following.
$\quad T(n) \approx{} T(n-1)$
$\quad T(n-1) = T(n-1)\*T(n-2)$
$\quad T(n-2) = 1$ if $T(n-1)$ is not 0.
So $T(n)$ must be 0 or 1 from time to time . That is obviously false, however. For example, we can let $T(1)=T(2)=2$.

---

### What to do?

What you can do is, as gnasher729 suggested, "taking logarithm on both sides immediately", assuming $T(1)\>0$ and $T(2)\>0$, which can be assume generally when we are analyzing recurrence relations in computer science.

You can also, of course, dive into analysis by cases when $T(1)$ and $T(2)$ might be 0 or even negative.

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: The definition of weakest precondition for a non-deterministic language
In the classical IMP language, the definition of weakest precondition is:

```
definition "wp c Q s ≡ ∃t. (c,s) ⇒ t ∧ Q t"

```

This is stating that from state s, after executing c we get to a state satisfying Q. My question comes when handling the IF FI construct in the language of guarded commands (see selection command in Wikipedia). My guess is that in this case one needs to define:

```
definition "wp c Q s ≡ ∃t. (c,s) ⇒ t ∧ (∀ t'. (c,s) ⇒ t' ⟶ Q t')"

```

I wonder if this is correct and whether it is the standard way of writing it in the literature.

Currently, I'm having problems proving the weakest precondition definition for the sequential composition of commands:

```
"wp (c1;;c2) Q s = wp c1 (wp c2 Q) s"

```

So, I'm beginning to think my definition is wrong. Quoting wikipedia:

> the result of this function, denoted wp(S,R), is the "weakest" precondition on the initial state ensuring that execution of S terminates in a final state satisfying R.

so termination is required in the definition, and this is not properly imposed so far. There could be non-terminating branches.

# Answer
> 4 votes
First of all, the definition of weakest precondition you've mentioned might be a little bit confusing. Namely, remember that the weakest precondition, designates all *states* of a program, such that when the given command executes, the given postcondition is satisfied.

Therefore, your initial definition might be a bit confusing, in the sense that the weakest precondition `wp(s, Q)` is determined really based on a postcondition (which you have as `Q`) and a command (which you have a `c`) -- that is all that is needed to define weakest precondition (w.p.).

Having that said, a more natural definition of `wp(c, Q)` says that: $$ wp(c, Q) = \\{ \sigma \in \Sigma | \text{ex}\[c, \sigma\] \models Q \\} $$ the weakest precondition, given `c` and `Q`, is a set of all states, such that executing `c` (denoted simply by `ex` here) from those states, assuming the execution terminates (we will come back to that later), will lead to some state $\sigma$ for which the postcondition `Q` is satisfied.

Given that, the weakest precondition you've mentioned, namely

> "wp (c1;;c2) Q s = wp c1 (wp c2 Q) s"

is a valid formulation for w.p. for compositions, as, naturally, executing `c1` you want to end up in a state belonging to the weakest precondition of `wp(c2, q)`, which, in turn, means that after further executing `c2` (in the sequence) you will have to satisfy postcondition (again, with the assumption that both terminate).

Now, in terms of this weakest precondition formulation, while the quote

> ensuring that execution of S terminates in a final state satisfying R

might confuse you, this does not say that termination is encoded in the w.p. formulation. Specifically, it is not required: the definition of weakest precondition says, that, *if* the given command executes and *terminates*, from those states, the postcondition has to hold.

That is why this is part of something traditionally called "partial correctness" and not "total correctness", as it does not prescribe termination (but rather, effectively, works under assumption of termination).

---
Tags: reference-request, nondeterminism, semantics, formal-methods
---


title: Carpet into Box

text:
# Question
Title: Carpet into Box
Given a carpet of size a * b \[length * breadth\] and a box of size c * d, one has to fit the carpet in the box in the minimum number of moves. A move is to fold the carpet in half, either by length or breadth.

One can even turn the carpet by 90 degrees any number of times, won’t be counted as a move.

Example: Box = 6 * 10 Carpet = 8 * 12

Output: No of moves = 1

Fold the carpet by breadth, 12/2 so now carpet is 6\*8 and can fit fine.

My approach is to divide a larger side and see if it fits in to the box.and keep doing it.Is my approach valid?

# Answer
I am afraid your approach does not work.

Here is a counterexample. Box = 3 * 10 while Carpet = 4 * 8. One move is enough as you can fold the carpet by its width, reaching 2 * 8. If you fold the carpet by its length, 4 * 4 cannot fit into 3 * 10.

Here is the answer.

> $\min(\lceil\log\_2\frac{a}{c}\rceil+\lceil\log\_2\frac{b}{d}\rceil,\ \lceil\log\_2\frac{b}{c}\rceil+\lceil\log\_2\frac{a}{d}\rceil)$

---

By the way, "length" refers usually to the longer side of a rectangle while "width" the shorter side.
> 2 votes

---
Tags: algorithms, dynamic-programming, greedy-algorithms, number-theory
---


# Question
Title: Finding the equivalence classes of a language
I'm doing a problem where I need to find the $≡\_A$ equivalence classes of the language $$A = \\{ 0^{n}x \mid n \in \mathbb Z^+, x \in \\{0, 1\\}^\*, \text{ and } \\#\_0(x) ≥ n \\}. $$

The best way I've learned to find the equivalence classes from a formal language is to create an automation and minimize it. Is there a conventional way of finding the equivalence classes of a language more quickly and intuitively? Because I do not know the DFA for this problem. Thanks for the help!

# Answer
Your language is $01^\*0(0+1)^\*$, i.e., all words starting with 0 and containing at least one more 0.

Indeed, a word of the form $0y0z$ is in $A$ since we can take $n=1$ and $x = y0z$. Conversely, if $w = 0^nx \in A$ then $w$ contains at least $2n \geq 2$ many 0's, and starts with a 0.

Therefore the Myhill–Nerode equivalence classes of your language are: $$ \epsilon, 1(0+1)^\*, 01^\*, 01^\*0(0+1)^\*. $$
> 1 votes

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


# Question
Title: Why more and more languages do not have link stage when compiling?
As far as I know, only C, C++, and Objective-C (in most used languages) need a linker when compiling, languages like Java and C# don't have one, and it seems more and more modern languages do not have a linking stage nowadays.

1. Why?
2. If there's no linker, the code cannot turn into machine code, so languages without a linker must have a virtual machine to run on(things like JIT still need a vm), right?
3. Languages can call each other by using abi if both them has a linking stage, right?

# Answer
You seem confused about what a linker does. It does not produce machine code. It merely sticks together (links, if you will) pieces of machine code that have already been produced by a compiler (typically).

What you were probably thinking of is that a linker produces an *executable*, or at least that's what a linker like `ld` does. This was the point of `ld`: to take pre-compiled libraries (`.a` files in UNIX parlance) and combine them together with object files to produce executables so you wouldn't need to recompile a library for every program that used it.

That said, there's nothing that keeps a compiler from just outputting an executable directly, but I don't think that this is actually happening that commonly. I'm pretty sure most languages that compile to native code do still have a linking stage. They just don't require you to explicitly call it yourself. In fact, LLVM is a popular backend for modern languages targeting native code, and building a new linker is one of the projects of LLVM. The premise that modern languages, at least those that directly produce native code, don't have a linking stage is incorrect.

For languages that primarily target a VM, they may not use `ld`, but that doesn't mean they don't have linkers. The recent addition to Java of "modules" has lead to `jlink`. More fundamentally and historically, the most natural thing to call a linker in Java is the ClassLoader. It even mentions linking the class. This is a dynamic linker. It performs the link stage at runtime. Here's the description of linking from the Java Language Specification. Of course, as always, there's nothing that stops you from compiling Java to a native executable. In that vein, there's also nothing stopping Java bytecode from being machine code.
> 9 votes

---
Tags: compilers
---


# Question
Title: Isn't this language in $\mathrm{P}^{\mathrm{NP}}$?
For an undirected graph $G$, let us denote $\gamma(G)$ the chromatic number of $G$. Let us define for positive integer $n$, the language $$ L\_n = \\{\langle G\rangle : \gamma(G) = n\\}. $$ This is the language of undirected graphs with chromatic number $n$. I think $L\_n \in \mathrm{P}^{\mathrm{NP}}$, for any $n$.

My argument is the following. We can look at the language, $$ \mathrm{CHROMNUM} = \\{\langle G, k\rangle : \gamma(G) \leq k\\}. $$ It is clear that $\mathrm{CHROMNUM} \in \mathrm{NP}$, since we can verify an instance just by displaying an at most $k$-coloring of $G$.

Thus, consider oracle Turing machine $M^{\mathrm{CHROMNUM}}\_n$, which on input $G$, simply checks that $\langle G, n \rangle \in \mathrm{CHROMNUM}$ and that $\langle G, k \rangle \not \in \mathrm{CHROMNUM}$ for all $k \leq n$.

I've just read about $\mathrm{P}^{\mathrm{NP}}$, so I wanted to be sure that this kind of argument is correct.

# Answer
**Yes, your argument is correct.**

$\textbf{P}^\textbf{NP}$ is the class of problems which are Cook-reducible (i.e., polynomial-time Turing-reducible) to $\textbf{NP}$. A Turing reduction to $\textbf{NP}$ is simply a reduction with oracle access to a problem in $\textbf{NP}$, in this case the problem $\text{CHROMNUM}$.

In fact, using your reasoning and the fact that $\langle G, k \rangle \not\in \text{CHROMNUM} \implies \langle G, k' \rangle \not\in \text{CHROMNUM}$ for all $k' \le k$, you can prove that you only need *two* oracle queries (independent of $n$). That is, your reduction resumes to checking the following: $$\langle G, n \rangle \in \text{CHROMNUM} \land \langle G, n - 1 \rangle \not\in \text{CHROMNUM}$$ This means you only need *one* $\textbf{NP}$ query and *one* $\textbf{coNP}$ query (since checking if something is not in an $\textbf{NP}$ language is in $\textbf{coNP}$). As it turns out, there is a class of problems which are characterized by having the same type of reduction, the difference polynomial time class $\textbf{D}^\textbf{P}$, and which, incidentally, coincides with the second level of the Boolean hierarchy.
> 4 votes

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


# Question
Title: How to find the spot which is furthest away?
Last night I thought about the following problem:
**Given any map (for example from Germany), how to find the spot which is furthest away (in every direction) from the nearest (any) town/village?**
I thought about how one would proceed to figure out in which problem class this problem belongs to and how to prove that.
And also how to determine which would be an efficient algorithm for this problem.
Basically I would like to learn about the steps how a professional in complexity theory would start to work on a problem like this.
I read on Wikipedia about the Nearest neighbor search which I think come close to what I'm looking for. But I wasn't able to find something like "furthest neighbor search".

# Answer
As you get further from Germany, you will get points which are farther and farther away. So unless you are taking into account the spherical nature of Earth, we need to change the problem, and look for a location *in Germany* which is farthest away from all villages in Germany. This is known as the largest empty circle problem, and can be solved essentially by computing the Voronoi diagram of the set of villages in Germany.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Using bit arrays to solve crossword puzzles
I have read *Crossword Puzzles and Constraint Satisfaction* by Connor, Duchi and Lo and I am trying to implement this variation of crossword solving algorithm. I can't understand the bit array data structure described on page 3, under "Lexicon". Could someone please give me an example?

PS: I have already implemented an efficient crossword solving algorithm but now I want to get even more serious in this difficult task.

# Answer
Suppose we are looking for the set of all words of length 5 with *a* in first position and *b* in second position (an example is the word *about*).

Our lexicon contains up to $N = 2000$ words of each length. For each length, for each position in the word, and for each possible letter, we store the set of words of given length in which the letter at the given position is the given letter.

For example, suppose that there are 100 words of length 5. We identify these words with the numbers 1,2,...,100. There is an array of length 100 in which the $i$'th value is 1 if the $i$'th word starts with *a*, and 0 otherwise. There is another array of length 100 in which the $i$'th value is 1 if the second letter of the $i$'th word is *b*, and 0 otherwise. We can take these two arrays and compute their entrywise AND: $$ \begin{array}{l|l} \text{First array} & 01110010\ldots \\ \text{Second array} & 11010011\ldots \\\hline \text{Result} & 01010010\ldots \end{array} $$ The $i$'th value of the new array is 1 iff the $i$'th word starts with *ab*.

Bit arrays are a space-efficient way to store Boolean arrays like the two arrays considered above, which also support fast operations like bitwise AND. The idea is simple – you store every value as one bit.
> 3 votes

---
Tags: data-structures, arrays
---


# Question
Title: Find the language from a context free grammar
I am having trouble determining the language from a given context free grammar. I've been given a hint that there are 2 parts to the language but can't figure either out.

$$G= (\\{S,A,B,C,D,E,Z\\},(0,1),R,S),$$

$\quad S\to E\mid Z$
$\quad E\to A\mid C $
$\quad A\to 01B\mid 0A\mid\epsilon$
$\quad B\to 1B\mid 10A $
$\quad C\to 10D\mid 1C\mid\epsilon$
$\quad D\to 01C\mid 0D $
$\quad Z\to 0Z1\mid e$

I have figured out $Z$ always produces a string with an equal number of 0s and 1s.

# Answer
A basic way to understand the language generated by a formal grammar is to understand the grammar, part by part.

In particular, for a context-free grammar, each non-terminal can be treated as the starting non-terminal and, hence, can be used to derive a context-free language. For example, starting from $Z$, we have only one rule, $Z\to 0Z1\mid\epsilon$. As you have found, $Z$ represents $L\_Z$, the language of words of zero or more number of 0's followed by the same number of 1's.

$S\to E\mid Z$ means $L\_S=L\_E\cup L\_Z$. What is nice about this union? The set of production rules starting from $E$ is disjoint from the set of production rules starting from $Z$. So we can analyze $L\_E$ and $L\_Z$ separately.

What is $L\_E$? $E\to A\mid C$ means $L\_E=L\_A\cup L\_C$.

What is $L\_A$? Here are the rules that starting from $A$.
$\quad A\to 01B\mid 0A\mid\epsilon$
$\quad B\to 1B\mid 10A$

You are supposed to play with these two rules for a while. What are the words in $L\_A$? Here are some of them. $\epsilon$, 0, 00, 000, 0110, 0000, 01110, 00110, 01100, 00000, 0001 10, 011100, 001110, 001100, 011110, 011000, 0110000, 0011000, 0111000, 01100110. If you have played that much, you will probably have a pretty good idea about the pattern.

Here is a way to see what is happening.

* $A$ can be empty word because of the rule $A\to\epsilon$.
* We can add one or more 0's before $A$ because of rule $A\to 0A$.
* From $A$, we can add 10 before it, turning it into $B$ because of rule $B\to 10A$. Then we can add zero or more 1's before that $B$, keeping it as a $B$ because of the rule $B\to 1B$. Then we can add 01 before it, turning it back into $A$.

We can repeat the process of turning $A$ to $A$ any number of times as well as finally turning $A$ to the empty word . So $L\_A\supseteq(0+011^\*10)^\*$, which is, in fact, an equality. $L\_A$ is the language of words without lonely 1's and with at least two 0's between any two groups of 1's which start and end with 0 except the empty word.

The above method seems ad-hoc. That is something that should be done whenever there is time to playing with rules and observing patterns.

Another approach is to observe the rules starting from $A$ have only one terminal on the right hand side. Furthermore, that one terminal only appears once and at the end. That means the grammars for $A$ is an extended right regular grammar. "There is a direct one-to-one correspondence between the rules of a (strictly) right regular grammar and those of a nondeterministic finite automaton, such that the grammar generates exactly the language the automaton accepts". I will encourage you to explore that correspondence. There are systemic ways to compute regular expressions from NFA.

The above should give you enough hint and direction to complete the rest of the task such as figuring out what is $L\_C$.
> 1 votes

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


# Question
Title: Proving a language as undecidable without using reductions
Let's say our Σ is 0 and 1. I want to disprove the following:

> There can be Turing Machines that accept only 1's, i.e. 1, 11, 111, etc. Therefore, all languages that have strings of 1's are recognizable.

My first step to proving this is by providing a language such as $One$, that accepts only if $w$ contains only $1$'s. There is a theorem that stated that $One$ is decidable iff $One$ and $\overline{One}$ are recognizable.

So, if I were to prove either one of them as unrecognizable, then I should be good. $\overline{One}$ I'll define as the set that doesn't contain 1 in it (i.e. episolon, 0, 00, etc). Creating a turing machine that simply goes right and accepts if we reach end without hitting a one, rejects if we do hit a one seems to work for this case. Could a language be created that isn't recognizable?

# Answer
> 1 votes
(I would post this as a comment but I need 50 reputation to comment... so...)

I think this might be solved using cardinality,
You have $2^{\aleph\_0}$ languages of such property (power set of $\\{ 1^n | n\>0 \\}$).
While $|RE| = \aleph\_0$

# Answer
> 2 votes
> It isn't recognizable because it is infinite, therefore it'll loop infinitely. Does this work?

No, because that claim is false. And your writing isn't at all clear, here. Recognizability is a property of languages, so your first two "it"s must refer to languages; but "loops infinitely" is a property of Turing machines, so your third "it" must be one of those.

Ultimately, though, your whole approach is doomed because the languages you call $One$ and $\overline{One}$ are both decidable. You can easily see that $One$ is decidabe just by designing a Turing machine that decides it.

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


# Question
Title: Find an invariant in the minimum algorithm
I have the following simple algorithm to find the smallest element of an array $A$ of numbers:

```
m = A[0];
For i = 0 to A.length() do
    if m < A[i] then
        m = A[i];
    end
end
return m;

```

The complexity of this algorithm is $O(n)$ where $n$ is the length of $A$.

I would like to prove the correctness of this algorithm using an invariant. Yet I don't know which invariant is nice here. Maybe something like: $m$ is the minimum of the subarray $A\[1..k\]$.

# Answer
> 1 votes
The invariant is good (once you fix lots of imprecise things, like the 1..k which is obvious nonsense, and wouldn’t proof correctness. Precision is important. ) The code is broken, so your proof should fail - because it would be an invariant of a correct algorithm, but not *your* code posted here.

---
Tags: algorithms, correctness-proof, loop-invariants
---


title: Why is A(A+B) = A [Absorption Law]?

text:
# Question
Title: Why is A(A+B) = A [Absorption Law]?
Could you proof it to me that A(A+B) = A?

AA + BA \[AA = A\]

A + AB

Then what?

# Answer
> 4 votes
I presume you are looking for a way to prove the identity using a calculus. So far you have used distributivity an idempotency.

Recall that `A = A1` so you get `A1+AB` and you can use distributivity again, this time in the other direction. Then two obvious steps.

# Answer
> 4 votes
Here is a proof: $$ A \stackrel{(1)}= A \cdot 1 \stackrel{(2)}= A \cdot (1+B) \stackrel{(3)}= A \cdot 1 + A \cdot B \stackrel{(4)}= A + A \cdot B \stackrel{(5)}= A \cdot A + A \cdot B \stackrel{(6)}= A \cdot (A+B). $$

Axioms used:

(1),(4) multiplicative identity

(2) absorption

(3),(6) distributivity

(5) idempotence

# Answer
> 2 votes
I always liked the $\min, \max$ definitions of $\cdot$ and $+$, since some courses in boolean algebra just give those laws and ask you to accept them. \[Boolean Algebra: Basic Operations\]

\begin{align\*} x \land y &= x \cdot y = \min(x,y)\\ x \lor y &= x + y = \max(x,y) \end{align\*} where $0 \leq x,y \leq 1$.

So $A(A+B)$ becomes: $$ \min(A, \max(A,B)) $$

* **Case 1:** If $A \leq B$ then

\begin{align\*} \min(A, \color{red}{\max(A,B)}) &= \min(A, \color{red}{B})\\ &= \min(A, B) = A\\ \end{align\*}

* **Case 2:** If $A \geq B$ follows the same way as the first one.

# Answer
> -1 votes
* A(A+B) as The AND operation distributes
* over the OR operation
* for all x, y, z ∈ B
* x • (y + z) = (x • y) + (x • z) so
* A(A+B) = AA+AB Idempotent x • x = x
* = A+AB
* = A(1+B) as 1+B=1 so
* = A(1) as A.1=A so
* = A

---
Tags: boolean-algebra
---


# Question
Title: What is Ironic complexity? What are some good resources to learn about it?
The term "Ironic complexity" was coined by Scott Aaronson for the stuff Ryan Williams does in the area of complexity theory. Could anyone tell me what kind of problems and approaches does Ryan Williams work upon? And is there a survey or course on it for self-study?

# Answer
> 7 votes
Here is a quote from Scott Aaronson's survey on the P vs NP question, in which he coined this term:

> There is one technique that has had some striking recent successes in proving circuit lower bounds, and that bypasses the natural proofs, relativization, and algebrization barriers. This technique might be called “ironic complexity theory.” It uses the existence of surprising algorithms in one setting to show the nonexistence of algorithms in another setting. It thus reveals a “duality” between upper and lower bounds, and reduces the problem of proving impossibility theorems to the much better-understood task of designing efficient algorithms.

The survey contains some pointers which you might want to look at.

Ryan Williams has given a series of two talks on this recently at the Simons institute: part 1 and part 2.

---
Tags: complexity-theory, lower-bounds, p-vs-np
---


# Question
Title: Longest simple walk below a certain weight
Given a directed graph G and a starting vertex $v$ and a cutoff weight $w$, I want to find a simple walk with net weight \< $w$ that visits as many nodes as possible. Currently, I have a recursive function which is incredibly slow, is there some sort of heuristic function for such a problem?

For my particular purposes, I am looking at superpermutation graphs for k letters, $S\_k$, with only 1-edges and 2-edges. $S\_k$ is vertex transitive, with each vertex having one 1-edge (weight 0) and one 2-edge (weight 1).

# Answer
> 1 votes
Without the "vertex-transitive" restriction, the problem is NP-hard, by reduction from Hamiltonian path.

Without the "vertex-transitive" or "number of neighbors" restrictions, the reduction is easy: set $w$ equal to the number of vertices minus one, and assign weight 1 to all edges. To accommodate the restriction on the number of neighbors, replace each node with a network of nodes shaped like two trees connected at their roots; each in-edge connects to a leaf of the first tree, and each out-edge connects to a leaf of the second tree, and put weight 0 on all the tree edges.

I don't know if this reduction can be extended to handle the case of vertex-transitive graphs as well.

---
Tags: graphs, shortest-path, heuristics
---


# Question
Title: Why are we interested in square-free words?
There is wikipedia page about square-free words, and there are a lot of theorems about these words, and examples of infinite square-free words.

I am wondering: why are we interested in these words?

Are there real-life applications of these words? Why are square-free words more useful to consider than other words?

# Answer
Well, take a moment to reflect. Is a word or a string one of the most important and most common entities in this world? What are the most basic properties of a word or string?

* its alphabet
* its length
* its sound
* its meaning
* its syntax or grammar
* its origin
* its usage as how to form sentences.
* hmm, does it repeat part of itself? Or never (square-free)?

It looks like the property of being square-free is almost a fundamental property of a word (or a phrase, or a sentence).

In fact, it is amazing to me that the formal study of square-free words has not made it way into most of textbooks about the theory of automata and computation. It appears that the study of square-free words turns out to be a rather isolated field with less impact.

Nevertheless, the study of square-free words and related concepts is interesting and fruitful, as you have observed. I am, for one, charmed by the square-free words of infinite length over three letters .

"Real-life" application related to square-free words are sparse indeed. *Abelian square-free words in algorithmic music* by Laakso, T. might count as one; however, I cannot find that paper. (Gefwert, C., Orponen, P., Seppänen, J. (eds.) *Logic, Mathematics and the Computer*, vol. 14, pp. 292–297. Finnish Artificial Intelligence Society, Symposiosarja, Hakapaino, Helsinki).

---

Here are two related exercise to entertain your mind.

An abelian square is a subsequence of the form $s\_1s\_2$ where $s\_2$ is a permutation of $s\_1$. For example, $abcbac$ is an abelian square since $bac$ is a permutation of $abc$.

**Exercise 1.** (easy) Let the alphabet consist of 3 letters. Show a word of length 7 that is free of abelian square. Show that every word of length eight contains an abelian square.

**Exercise 2.** (very very hard) There is an infinite abelian-square-free word over an alphabet of size four.
> 3 votes

# Answer
Under related concepts on the wiki page for square-free we find the notion of cube-free words. An example of such words is the (Prouhet-)Thue-Morse sequence. Which has a very real-life application.

> The sequence has been discovered independently many times, not always by professional research mathematicians; for example, Max Euwe, a chess grandmaster, who held the World Championship title from 1935 to 1937, and mathematics teacher, discovered it in 1929 in an application to chess: by using its cube-free property (see above), he showed how to circumvent a rule aimed at preventing infinitely protracted games by declaring repetition of moves a draw.
> 3 votes

---
Tags: word-combinatorics
---


# Question
Title: Sort 2D arrays so that cost of reaching new position as described at each iteration is minimized
Problem is as following:

We are 8 trumpet players in an orchestra.

There are for example 4 parts so there are always two players on the same part.

Now, there are not always the same two players playing the same part meaning the combination of players that play the same part change from piece to piece.

What is the cheapest way in terms of distance and/or the least amount of switches resulting that the players playing the same parts can sit next to each other on every piece?

---

Trumpet Players: a,b,c,d,e,f,g,h

Parts: 1,2,3,4

Seats are arranged like that:

```
1st piece
| a1 | b1 | c2 | d2 |

| e3 | f3 | g4 | h4 |

Next piece the players might play the following parts:
| a2 | b1 | c3 | d1 |

| e3 | f4 | g2 | h4 |

and the next one againt different distribution of the parts:
| a4 | b3 | c1 | d3 |

| e2 | f4 | g2 | h1 |

```

how do we seat the players so that the least amount has to be traveled in order to reach the desired positions for the players playing the same parts to sit next to each other in the next piece?

additional notes: i dont care where the pairs are starting and if a1 sits left of b1 or the other way around.

# Answer
I would suggest using the A\* algorithm. The state is where each player is currently seating and the number of pieces you've played so far. Each edge represents a way that you can update the seating. Also, when you're in a state where, for the next piece to be played, everyone is sitting next to their partner on that piece, you can increment the number of pieces played at 0 cost. The start state has 0 pieces played, and the goal state is any state where you've played all the pieces. Then, A\* will find the lowest-cost sequence of movements to complete the concern.

You'll need an admissible heuristic to estimate the cost to finish the concert, starting from a particular intermediate state. One very simple heuristic is: count the number of players who will have some future piece to play, where they're not currently sitting next to their partner on that piece, and divide by two. Perhaps a slightly better heuristic is to count, for each player, the number of future partners (for any piece not yet played) who they are not currently sitting next to, and divide by four. Assuming each switch costs one and there is no other way to update the seating, this is admissible, as each switch can only decrease this count by at most four.
> 1 votes

---
Tags: sorting, arrays
---


# Question
Title: In which category is the supercomputer SUMMIT according to Flynn's taxonomy?
I have read that the POWER9 processor is an SIMD processor. I have also read that most supercomputers are MIMD based.

So is the SUMMIT supercomputer SIMD? And if it is can you name a supercomputer that is MIMD?

# Answer
> 2 votes
Summit is a parallel system that apparently contains many nodes, where each node is powered by one or more POWER9 processors. Each POWER9 processor contains a vector scalar unit that Wikipedia says can be described as a SIMD unit. However, the Summit system as a whole would normally be used in a MIMD mode, as each POWER9 processor can run a separate program. It doesn't have to -- you could run the same code on each node, or different code on each node -- but each node runs asynchronously and independently, so I would classify the entire system as MIMD.

---
Tags: computer-architecture
---


title: Constructing CFG

text:
# Question
Title: Constructing CFG
How to generate CFG for this language?

$ L = \\{ w \mid w \in \\{ (, \[, \], ) \\}^\* \text{ s.t. } $

* In any prefix of $w$, no. of ( is more than no. of ), and
* no. of \[ is more than no. of \].

$\\}$

Thus, (\[(), \[()\[\] etc. are valid.

I have tried,

$ S \to (S \mid (S)S \mid \[S \mid \[S\]S \mid \epsilon $

But, this does not accept, (\[)\].

It seems possible to do with two stacks, by keeping counts of ( and \[. Thus it seems it is not Context Free. Any help in proving it is not CF or a CFG exists?

# Answer
The language is not context-free, as you have suspected.

Intuitively, a PDA that accepts the language has to keep track of the difference of the number of (s and the number of )s as well as the difference of number of \[s and the number of \]s. Since these two differences vary to arbitrary largeness independently to each other, one pushdown stack is not able to track them. However, this understanding is not a rigorous proof.

One standard way to disprove context-free-ness is to tap into the power of the pumping lemma. A bit of care should be taken to construct the witness word. For example, a word of the form $(^{p+1})^p\[^{p+1}\]^p$ or $(^{p+1}\[^{p+1}\]^p)^p$ can be pumped without any problem. However, that word is not far from the right word we need.

In case a more explicit hint is needed, here it is.

> Check $(^{p+1}\[^{p+1})^p\]^p$ assuming the pumping length is $p$.
> 1 votes

---
Tags: turing-machines, automata, context-free, formal-grammars
---


title: The recursion $T(n) = T(n/2)+T(n/3)+n$

text:
# Question
Title: The recursion $T(n) = T(n/2)+T(n/3)+n$
I'm looking at the reccurrence $$T(n) = T(n/2) + T(n/3) + n,$$ which describes the running time of some unspecified algorithm (base cases are not supplied).

Using induction, I found that $T(n) = O(n\log n)$, but have been told that this is not tight. Indeed, assume inductively that $T(k) \leq Ck\log k$ for all $k\<n$ (and sufficiently large values of $k$), then

\begin{align\*} T(n)&\leq C\frac{n}{2}\log\frac{n}{2} + C\frac{n}{3}\log \frac{n}{3} + n\\ &= C\frac{5}{6}n\log n - n(C/2+C\log3/3 - 1). \end{align\*}

Now I choose $C$ large enough for $(C/2+C\log3/3 - 1) \> 0$, and so the last expression is dominated by $C\frac{5}{6}n\log n\leq Cn\log n$.

My first question is, what is a tighter bound that this?

Second, I tried to use the Akra-Bazzi method to solve this, so let $p$ solve $$\left(\frac{1}{2}\right)^p + \left(\frac{1}{3}\right)^p = 1.$$ Then approximately $p=0.79$, and (with $g(n) = n$) I get $$\int\_1^n \frac{g(u)}{u^{p+1}} du = \int\_1^n \frac{1}{u^{p}} du = \frac{1}{1-p}(n^{1-p}-1),$$ and so

$$T(n) = \Theta\left(n^p\left(1+\frac{1}{1-p}(n^{1-p}-1)\right)\right).$$

This equals $\Theta(n^p + \frac{1}{1-p}n-\frac{1}{1-p}n^p)$, so overall $\Theta(n)$, since $p\<1$. My second question is that I don't really believe that $T$ is linear, so what went wrong in my application of Akra-Bazzi?

Best regards.

# Answer
If $T(1)\le 6$ and $T(2)\le 12$, we can show that $T(n)\le 6n$ by induction.

$$T(n) = T(n/2) + T(n/3) + n \le 6(n/2)+ 6(n/3)+n= 6n.$$

More generally, let $c\gt6$ be a constant such that $T(1)\le c$ and $T(2)\le 2c$, then we can prove routinely that $T(n)\le cn$. Although it might seem unbelievable to you, it is true that $$T(n)=O(n).$$

Intuitively, since $\dfrac12+\dfrac13\lt1$, the terms $T(n/2)$ and $T(n/3)$ is not big enough to lift $n$ to a power of $n$ of a larger exponent.

There is nothing wrong in your application of Akra-Bazzi method, which tells us that $T(n)=\Theta(n)$.
> 6 votes

# Answer
Let $S(n) = T(n)/n$. Then $S(n)$ satisfies the recurrence $$ S(n) \leq \frac{1}{2} S\left(\frac{n}{2}\right) + \frac{1}{3} S\left(\frac{n}{3}\right) + 1. $$ In particular, if $C$ satisfies $$ \frac{1}{2} C + \frac{1}{3} C + 1 \leq C $$ then $S(n/2),S(n/3) \leq C$ would imply $S(n) \leq C$. This is the case for all $C \geq 6$.
> 4 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: From where does the Fetch Unit get its instructions?
In the ARM Architecture pipelining stages, we know that the instructions pass from fetch to decode and so on? But, from where does the fetch unit get the instructions?

# Answer
> 2 votes
The instructions come from some part of memory, pointed to by the Program Counter (PC) aka Instruction Pointer (IP).

In modern computers, instructions tend to share the same RAM used for everything else (with protections in place to keep things sane), but especially in older or special-purpose machines it's not uncommon for instructions to be baked into ROM instead.

---
Tags: computer-architecture, cpu-pipelines
---