# Question
Title: How to find every negative cycle in a graph
A graph with n vertices, no matter directed or not, may have maximally 2^n-n-1 negative cycles

(Think about combination of 2 to n elements and you'll figure out why 2^n-n-1. A graph that has no graph loops or multiple edges is my only concern)

and I want to find ALL of them if any, not just one of them. There are only answers to the latter question throughout the whole internet. To find a cycle means we get a list of vertices which form this cycle.

I also want to find the one negative cycle which is the smallest in one lap of traverse.

One solution, which is slow and not elegant, is to run Floyd-Warshall algorithm on the graph, and find those vertices, e.g. i, so that d\[i\]\[i\]\<0 (According to some researches collected in Wikipedia, this means vertex i is part of a negative cycle) and then check all 2^n-n-1 (if there are n of those i's) cycles to see if they are negative.

# Answer
First of all, there can be exponentially many negative cycles, as @Steven already mentioned. Take $K\_n$ with only negative edges. Enumerating all of them will be bound to take exponentially long time.

You also say that you want to find the *most negative cycle* in the graph (which should be simple if you enumerate them all), however, in case you want a special algorithm for this problem, note that this problem is NP-complete; the reduction from *Hamiltonian* is straight forward.

Since you ask for *any algorithm*, just run, for every subset of vertices, a DP algorithm to find the Minimum Hamiltonian Cycle for that induced subgraph. (Since you don't want to revisit an edge, you can probably find a way to add $\min\_{e \in E(G)} w(e)$ to every edge, thereby avoiding all the negativity.)

(P.s., OP stated in a comment that cycles on the same vertex set are considered equivalent.)
> 2 votes

---
Tags: graphs
---


title: Two definitions of Safe Edge

text:
# Question
Title: Two definitions of Safe Edge
I ran into an interview two days ago and came across one strange definition of safe edge.

We are given an undirected weighted Graph $G = (V,E)$ with all distinct edge weights. Assume that the graph is connected.

> Safe Edge Definition: if an edge $e \in E$ is not contained in any cycle, we called it a safe edge

Following is a theorem based on the above definition.

> Theorem: All the safe edges must be in Minimum Spanning Tree (MST).

Please compare the definition of a "safe edge" on this interview with the classical definition of safe edge at all courses like here: MAIN SAFE EDGE THEOREM.

# Answer
> 5 votes
They are two different definitions. The interview definition calls a safe edge one that is not part of any cycle and therefore cannot be removed from $G$ without disconnecting it, thus changing the resulting MST. Notice that this definition depends solely on the chosen edge and on $G$. Notice also that it does not depend on the edge weights in any way.

The definition in the notes defines a safe edge $e$ as one that can safely be added to a subgraph $A$ of $G$ so that $A + e$ is a partial MST of $G$. In this case $A$ is probably thought to already be a partial MST of $G$, since otherwise no edge would be safe, although this is not formally required. Notice that this definition depends on the particular choice of $A$ and on the edge weights of $G$.

As an example, let $G$ be a cycle on $n$ nodes, where the $n$ edges have weights $1, \dots, n$. None of these edges is safe according to the interview definition. If $A$ is the empty graph then all edges except for the one of weight $n$ are safe w.r.t. the definition in the notes. If $A$ is the subgraph containing the edge of weight $n$ then no edge is safe w.r.t. the definition in the notes.

---
Tags: graphs, trees, minimum-spanning-tree
---


title: Cache read controller

text:
# Question
Title: Cache read controller
Does the cpu interface with a memory controller to read the cache? What happens when data is not in the cache, a cache miss, does it automatically fetch the data?

# Answer
Information about on die structures are scarce for the intel CPUs. You can look at https://en.wikichip.org/wiki/amd/microarchitectures/zen#Memory\_Controller for information on AMD CPUs. Especially the following images:

You have the actual die seen under a microscope for the Zen microarchitecture. You clearly see the L3 and L2 controllers. There is one L2 cache per core while there is a shared big L3 cache in the middle.
> 1 votes

---
Tags: cpu-cache
---


title: Lexicographically Smallest String

text:
# Question
Title: Lexicographically Smallest String
**Problem Statement**: Given a string/pattern only consisting of **'\<'** and **'\>'** symbol, find the **lexicographically** smallest string that satisfies the pattern(made up of only lowercase english alphabets). Some examples are given below for better understanding.

**Examples**:

1. *Input*(String) - '**\>\>**'
*Output*(String) - '**cba**' (because c \> b \> a)
2. *Input*(String) - '**\>**'
*Output*(String) - '**ba**' (because b \> a)
3. *Input*(String) - '**\>\<\>**'
*Output*(String) - '**badc**' (because b \> a \< d \> c)

**Constraints**: String/Pattern length is always \<= 25 and in the output string, no alphabet should be repeated.

I am unable to come up with any approach which has a lesser complexity than **O(N!)**(which would surely never pass the time limits), N being the given string/pattern's length. Any help is appreciated.

**P.S.** \- This problem was asked in a HackerEarth hiring contest, and no, the contest is no longer live.

# Answer
> 2 votes
Let us denote the solution for a string $w$ and a set $A$ of remaining letters by $s(w,A)$. Also let $A = a\_1 \< \cdots \< a\_n$. If $w$ equals $\>^{n-1}$ then clearly the solution is $a\_n a\_{n-1} \ldots a\_1$. If $w$ starts with a run of $\ell$ many $\>$'s (possibly $\ell=0$), then the first $\ell+1$ letters of any solution must be $a\_{\ell+1} \ldots a\_1$ or lexicographically larger. Conversely, there always is such a solution – we can construct one recursively. This shows that $$ s(\>^\ell\<x,\\{a\_1,\ldots,a\_n\\})=a\_{\ell+1}\ldots a\_1 s(x,\\{a\_{\ell+2},\ldots,a\_n\\}), \quad s(\>^{n-1},\\{a\_1,\ldots,a\_n\\}) = a\_n \ldots a\_1. $$ Since this greedy construction always "eats away" a prefix of the alphabet, it can easily be implemented in linear time.

---
Tags: algorithms, data-structures, algorithm-analysis, string-manipulation
---


title: Asymptotic growth of a series

text:
# Question
Title: Asymptotic growth of a series
How we can prove that: $$ \sum\_{k=1}^{c \log n-1}\\:k\cdot \left(\frac{1}{2}\right)^{\frac{k}{3}}\in O\left(1\right) \quad \mbox{?} $$

# Answer
> 2 votes
$$ \begin{align\*} \sum\_{k=1}^{c \log n - 1} k 2^{- \frac{k}{3}} &\le \sum\_{k=1}^{c \log n } k 2^{- \lfloor \frac{k}{3} \rfloor } \le \sum\_{k=1}^{\lceil \frac{c}{3} \log n \rceil} 3k 2^{-k+1} \le 6\sum\_{k=0}^{\infty} k 2^{-k} \\ &\le 6\sum\_{k=0}^{\infty} \left( \frac{3}{2} \right)^k 2^{-k} = 6 \sum\_{k=0}^{\infty} \left( \frac{3}{4} \right)^k = 6 \cdot 4 = 24 \in O(1). \end{align\*} $$

---
Tags: time-complexity, hash-tables, average-case, time-series-analysis
---


title: Are all finite languages context-free?

text:
# Question
Title: Are all finite languages context-free?
As far as I know, finite languages have a finite number of strings or words, while context-free languages are generated by context-free grammars. I don't know which aspect should I know that they are correlated with. All I know is that finite languages are regular, and regular languages are context-free. How should I know this?

# Answer
> 17 votes
The language consisting of the words $w\_1,w\_2,\ldots,w\_n$ is generated by the context-free grammar $$ S \to w\_1 \mid w\_2 \mid \cdots \mid w\_n. $$

# Answer
> 1 votes
Let

* $F$ be the set of finite languages
* $R$ be the set of regular languages
* $C$ be the set of context-free languages.

The statement "All finite languages are regular" can be rewritten $F \subseteq R$. Similarly, "All regular languages are context-free" can be rewritten $R \subseteq C$. Both being true, we can take $F \subseteq R \land R \subseteq C$ to be true as well.

Set inclusion is known to be a transitive relation, that is $F \subseteq R \land R \subseteq C \rightarrow F \subseteq C$. Thus, by modus ponens, we can conclude that $F \subseteq C$ is true, or that all finite languages are context-free.

---
Tags: context-free
---


# Question
Title: Data structure for or-lookups over bit-field associations maps
For a mapping between a bit-arrays and values I want cheap lookups using bitwise-or instead of equality.

Slightly more formally, I have a set of associations $k\_i \mapsto v\_i$ where $k\_i \in \mathcal{P}(\mathbb{N})$ is a set of naturals and $v\_i$ can be of any type $T$. A query on $q \in \mathcal{P}(\mathbb{N})$ matches pairs $(k\_j,v\_j) \in \mathcal{P}(\mathbb{N}) \times T$ such that $k$ overlaps with $q$ (ie $q \cap k \neq \varnothing$). Also the maximum element $M$ encountered in any $k\_i$ is bounded, typically not larger than 5k and each $k\_i$ is small $|k\_i| \ll M$, ie the bitfield corresponding to the set $k\_i$ would be sparse.

I imagine it could be a tree or a heap with `(bitfield,a)` values at the leaves and at each node a bitfield that is the bitwise-or combination of all bitfields in it's subtree? I failed to find any literature on the subject. Any pointers?

# Answer
Preprocessing: For each $(k\_i, v\_i)$ pair, and for each $x \in k\_i$, add $(x, (k\_i, v\_i))$ to a map data structure (e.g., a hashtable) with $x$ as the key.

To process a query $q$, for each $y \in q$ look up all values in the map, append all of them to a list, and finally remove duplicates (or instead add them directly to a data structure that can collapse duplicates immediately, like a hashtable).
> 1 votes

# Answer
Unfortunately I'm not aware of any data structure that will have better worst-case running time than a naive approach of simply a linear scan through the entire list of associations.

Therefore, if you want to solve this in practice, you will have to hope for some kind of structure that you can take advantage of (e.g., that most sets are sparse, that there are usually few overlaps, or something like that), and we won't be able to suggest algorithms without knowing those specifics.
> 0 votes

---
Tags: data-structures, sets, bit-manipulation
---


# Question
Title: Convert an IF statement in Mixed Integer Programming
I want to convert an IF statement for my optimization problem. I want to minimize the total price. I want 800 tones of salt and 3 suppliers offer me their prices.

Supplier $1$ offers me $100$ tones at $\\\\$150$ a tone.

Supplier $2$ offers me $400$ tones at $\\\\$170$ a tone, if I take $300$ tones (or more)the price drops to $\\\\$150$.

Supplier $3$ offers me $1600$ tones at $\\\\$170$ a tone.

Here is my model without the if statement :

$x\_i$ is an integer variable representing the quantity bought to the supplier $i$, $p\_i$ is the price of the supplier $i$, $c\_i$ is the maximal capacity offered by the supplier $i$.

$Min( p\_1\times x\_1 + p\_2\times x\_2 + p\_3\times x\_3)$

$s.t. x\_1 + x\_2 + x\_3 = 800$

$ x\_1 \leq 100$

$ x\_2 \leq 400$

$ x\_3 \leq 1600$

Now I want to use the *Big M method* the convert my if statement but I don't know how to do it. I tried this method : Express a "complex" IF-Statement to Linear Programming to find the constraints but I don't know how to modify my prices. I tried this :

If $x\_2 \geq 300$, Then $p\_2 = 150$, Else $p\_2 = 170$.

i.e.

If $x\_2 \geq 300$, Then $b = 1$, Else $b = 0$ and $p\_2 = 150b + 170(1-b)$

In addition to this I code in python the the mip library, do you know a better library to do this?

Thanks a lot !

# Answer
> 0 votes
Let $x\_i$ represents the quantity bought from the $i$-th supplier, and consider the following scenario: the price of the 2nd supplier is 170\\$ per tonne but, if you buy at least 300 tonnes, then you get to choose a non-negative quantity $d \le x\_2 - 300$ and you get a 20\\$/tonne discount on $d$ tonnes, otherwise $d=0$ (i.e., you get no discount). Clearly this is equivalent to your original problem since, given $x\_1, \dots, x\_3$, it is always convenient to maximize $d$.

You can model this as follows:

$$ \min 150x\_1 + 170 x\_2 + 170x\_3 - 20d \quad \mbox{s.t.}\\\\[6pt\] \begin{align\*} x\_1 &\le 100 \\ x\_2 &\le 400 \\ x\_3 &\le 1600 \\ x\_1 + x\_2 + x\_3 &= 800 \\\\[6pt\] 100 y &\> x\_2 - 300 & (1)\\ 300 y &\le x\_2 &(2)\\\\[6pt\] d &\le x\_2 - 300y &(3)\\ d &\le 100y &(4)\\\\[6pt\] x\_1, x\_2, x\_3,d &\ge 0 \\ y &\in \\{0,1\\} \end{align\*} $$

Notice that $y$ is a binary variable that equals $1$ if and only if $x\_2 \ge 300$. Indeed, if $x\_2 \ge 300$ the constraint $(1)$ is satisfied only when $y=1$ (recall that $x\_2 - 300$ is at most $100$), and the constraint $(2)$ simplifies to $300 \le x\_2$, which is true. If $x \< 300$ then the constraint $(2)$ forces $y=0$ and the constraint $(1)$ simplifies to $0 \ge x\_2 - 300$, which is true.

If $y=0$, then $d$ must be $0$, and this is enforced by constraint $(4)$ which becomes $d \le 0$ (recall that $d$ is non-negative), while $(3)$ is always satisfied. If $y=1$, then constraint $(3)$ enforces $d \le x\_2 - 300$, which also implies constraint $(4)$ since $d \le x\_2 - 300 \le 100 = 100y$.

---
Tags: integer-programming
---


# Question
Title: How to prove $T(n) = 2T(n/2) + n/\log(n)$ can't be solved using the Master Theorem?
I have read (in this question) that this recursion can't be solved via Master Theorem. But I couldn't find exact and complete proof why the Master Theorem does not apply.

# Answer
Your recursion can be written as: $$ T(n) = aT(n/b) + f(n), $$ where $a=b=2$ and $f(n) = n \log^{-1} n$. Defining $c\_{crit} = \log\_b a = 1$ you can see that $f(n) = \Theta( n^{c\_{crit}} \log^k n)$ for $k=-1$, therefore case 2b of the Master Theorem applies. The solution to the recurrence is therefore: $$T(n) = \Theta( n^{c\_{crit}} \log \log n ) = \Theta( n \log \log n).$$
> 0 votes

---
Tags: recursion, master-theorem
---


# Question
Title: Time complexity of comparing $N$ strings
I would like to double check myself.

As I understand time complexity of comparing two strings in the worst case is $O(n)$, where $n$ is the length of the strings (let's say they are equal length).

In case I have $N$ strings and I would like to know whether they are all different.

Is there an algorithm for this that is faster than $O(n \cdot N^2)$?

# Answer
You can sort the strings based on increasing or decreasing *lexicographic* order. Then, you can easily find the duplicate string by iterating over the set once, and checking if any two consecutive strings are the same or not.

Now, everything boils down to the sorting algorithm that you want to use. Consider these two popular options:

1. If you use **Merge sort**, it would take $O(N \log N)$ comparison operations. Since the length of each string is at most $n$, a comparison operation would take $O(n)$ time. Thus, the sorting takes $O(n \cdot N \log N)$ time.
2. You can also use **Radix sort**. It would take $O(n \cdot N)$ time. This is similar to the approach that is suggested by gnasher729. I am just explicitly mentioning the name of this technique.

It is easy to see that **Radix sort** is giving a better time complexity of $O(n \cdot N)$. Lastly, iterating over the entire set once and checking if any two consecutive strings are the same, takes $O(n \cdot N)$ time. Thus, the overall time complexity is $O(n \cdot N)$.
> 3 votes

# Answer
It’s much better. Say you have strings implemented as a sequence of 8 bit characters. You put each string into one of 256 bins depending on the first character. Then you examine the bins with more than one entry, by putting strings into bins depending on the second character and so on.

The worst case is all strings starting with the same $k$ characters for $k$ close to $n$; this is handled in $O(kN)$ steps. Your algorithm suffers badly in this case.
> 3 votes

---
Tags: time-complexity, strings
---


# Question
Title: How to analyse the worst-case time complexity of this algorithm(a mix of Bubble Sort and Merge Sort)?
Suppose I have a sorting algorithm that sorts a list integers. When the input size(the number of elements) $n$ is odd, it sorts using Bubble Sort and for even $n$ it uses Merge Sort. How do we perform the worst-case time complexity analysis for this algorithm?

The context in which this question came about is when I was going through the analysis of MAX-HEAPIFY algorithm given in CLRS(3rd edition) on page 154. In the worst-case analysis, the author had assumed some arbitrary input size $n$ and then concluded that the worst case occurs when the bottom-most level of the heap is exactly half full. This threw me off since in various texts and articles, $n$ is assumed to be fixed when performing the worst case analysis(and even for best or average cases for that matter) and that the number of elements at the bottom-most level of a heap of $n$ nodes is fixed. In that light, I concocted this algorithm so as to have the worst case dependent on $n$.

My intuition tells me that the worst case time complexity for this algorithm is $\mathcal O(n^2)$ since that's the worst case runtime for Bubble Sort. But I want to know the precise mathematical formulation of the worst-case time complexity analysis for any algorithm. Any insight would be much appreciated.

# Answer
Let $f(n)$ the maximum number of elementary operations performed by the algorithm when the number of elements to sort is $n$.

An upper bound to the worst-case complexity of the algorithm is $O(n^2)$ since there exists some $n\_0$ and some constant $c\>0$ such that for every $n \ge n\_0$, $f(n) \le c n^2$.

Moreover, given some other function $g(n) = o(n^2)$ it is false that $f(n) \in O(g(n))$ since for all $c\>0$, there always exists a sufficiently large $n$ for which $f(n) \ge c g(n)$. In this sense, $O(n^2)$ is the smallest asymptotic upper bound you can hope to obtain.

Notice however that with this choice of $f(n)$ it is not true that $f(n) = \Omega(n^2)$ according to Knuth's definition of big Omega, while it is true in the Hardy–Littlewood definition. The "problem" here is that $f(n)$ is not monotonically non-decreasing, while the functions considered in algorithm analysis usually are.

Of course you can define $F(n) = \max\_{0 \le n' \le n} f(n')$ to get a monotonically non-decreasing function, which is probably what you have in mind when you think of the worst-case running time of the algorithm.

Then you have: $F(n) = O(n^2)$ and $F(n)= \Omega(n^2)$ showing that $F(n) = \Theta(n^2)$.
> 1 votes

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


# Question
Title: Unique decipherability of infinite regular language
Can we design an algorithm to test if a infinite regular language is a code?

We have the S-P algorithm to determinate if a finite language is a code. But how about the infinite part of regular languages? If we have a regex which describes our set of words, then is it possible to modify the S-P algorithm to work on an infinite set without creating Pattern Matching Machines? If it helps, let the regex use only '\* | ()' as special symbols.

I thought about making an algorithm which would work based on a PMM, but it isn't as trivial as the S-P algorithm for finite sets, checking the suffixes of strings with matching prefix. The algorithm would be creating a PMM from the regex and traversing it for the search of suffixes etc. like in the S-P algorithm.

# Answer
McCloskey gave such an algorithm in his paper An $O(n^2)$ Time Algorithm for Deciding Whether a Regular Language is a Code. Given an NFA on $n$ states, his algorithm runs in time $O(n^2)$. Since a regular expression of length $n$ can be converted to an NFA with $O(n)$ states in linear time, McCloskey's algorithms runs in quadratic time even when given a regular expression as an input.
> 3 votes

---
Tags: regular-languages, automata, coding-theory
---


# Question
Title: Explain the difference between Turing Complete and Turing Equivalence
I'm not sure if I understand the difference between Turing Complete and Turing Equivalent programming languages.

> A computational system that can compute every Turing-computable function is called Turing-complete (or Turing-powerful).
>
> A Turing-complete system is called Turing-equivalent if every function it can compute is also Turing-computable; i.e., it computes precisely the same class of functions as do Turing machines.

I'm not sure if I understand the difference between these two terminologies properly and what "Turing-computable" means. So for example if I have a programming language $X$, it is Turing complete if it can do any and everything that a Turing Machine can do? And it $X$ ends up being Turing complete and it can be shown that all of the functions that it computes are Turing computable, then $X$ is also Turing equivalent?

# Answer
> 7 votes
A system is Turing-complete if it is at least as powerful as Turing machines.

A system is Turing-equivalent if it is exactly as powerful as Turing machines.

An example of a Turing-complete system which is not Turing equivalent is Turing machines with oracle access to an oracle for the halting problem.

One can come up with one additional definition to complete the picture: a system is *effective* if it is at most as powerful as Turing machines, that is, if every function computed by the system is computable by a Turing machine.

---
Tags: complexity-theory, turing-machines, computability, programming-languages, turing-completeness
---


title: XOR Statement in integer programming

text:
# Question
Title: XOR Statement in integer programming
How can I convert a XOR statement into linear constraints for integer programming ?

The expression is $(x\_1 \geq 1)$ XOR $(x\_2 \geq 1)$ where $x\_1$ and $x\_2$ are integer. It means that if $x\_1 \geq 1$ then $x\_2 = 0$ and vice versa.

I started to linearize the statement by : $(x\_1 \geq 1)$ XOR $(x\_2 \geq 1) = (x\_1 \geq 1 \quad and \quad x\_2 \leq 0) or (x\_1 \leq 0 \quad and \quad x\_2 \geq 1)$ but I don't know how to continue, I would like to follow the *Big M mothod* but I'm going around in circles...

I need it to resolve this kind of linear program where if $x\_1\geq 0$ then $x\_2=0$ and vice versa :

\begin{equation} \begin{aligned} \min \quad & a\_1x\_1 + a\_2x\_2 + a\_3x\_3\\ \textrm{s.t.} \quad & x\_1 + x\_2 + x\_3 = 200\\ &x\_1 \leq 100\\ &x\_2 \leq 100\\ &x\_3 \leq 100\\ &x\_1 \geq 1 \quad xor \quad x\_2 \geq 1 \\ &x\_i \in N, \quad i \in \\{1, 2, 3 \\} \\ &a\_i \in R, \quad i \in \\{1, 2, 3 \\} \\ \end{aligned} \end{equation}

Thanks a lot ! :)

# Answer
For binary variables you could just write $x\_1 = 1 - x\_2$, but I see that in your case $x\_1,x\_2 \in \\{1,2,3\\}$. You can still use the same trick once you force a boolean variable $y\_i$ to be 1 if and only if $x\_i \ge 1$:

$$ \begin{align\*} 3 y\_1 &\ge x\_1 \\ y\_1 &\le x\_1 \\\\[6pt\] 3 y\_2 &\ge x\_2 \\ y\_2 &\le x\_2 \\\\[6pt\] y\_1 &= 1-y\_2 \\\\[6pt\] y\_1, y\_2 &\in \\{0,1\\} \end{align\*} $$
> 1 votes

---
Tags: integer-programming
---


# Question
Title: Can every self-modifying algorithm be modelled by a non-selfmodifying algorithm?
If we have any arbitrary computer program that can modify its instructions, is it possible to simulate that program with a program that cannot modify its instructions?

---

**Edit:**

I am new to stackexchange so not sure if I'm allowed to ask a NEW question here, but here goes: Ok so the proof that it is possible is actually really simple as you guys have shown. Now, I am wondering: Are there problems for which it is more efficient (and to what extent) to use the most efficient self-modifying algorithm to solve the problem, versus the input-output-equivalent most efficient non-selfmodifying algorithm?

# Answer
Yes, it's possible. You can simulate the program by using an interpreter for the language it's written in. Now, the program (the interpreter) is fixed and the thing that used to be a self-modifying program is now the interpreter's data.

In particular, you could perfectly well have a universal Turing machine that allowed the TM it's simulating to modify its own description. (The description of the simulated machine, I mean; not the UTM.)
> 29 votes

# Answer
Any Turing-complete computational model that does not have modifying code (or "code") serves as a proof of that statement. I don't know that any of the standard models (TM, RAM, ...) *do* have modifying code, so we don't have to look too far.

To get a program in whatever language you have in mind, compile from such a model (and make sure that the compiler does not introduce code modification).

---

This is, of course, an existential argument: there *is* an equivalent program. But we also know that there are recursive (i.e. computable) compilers between any two Turing-complete languages, so that is how you get a program of the form (read: in the language) you want.
> 10 votes

# Answer
To add on to David Richerby's answer:

If it were true that no self-modifying algorithms can't be modeled by non-self-modifying algorithms, then those algorithms would have to be executed on something that's also self-modifying. It'd have to be turtles all the way down.

As I mentioned in my comment, a self-modifying algorithm can be executed on a processor that itself abides by the rules of a static algorithm (encoded in its design) which "tells" it how to execute machine instructions.
> 4 votes

# Answer
Of course you can unwind self modifying code to some sort of semantic equivalent version. However, self modifying code where timing and external state or internal cache behavior is part of what influences the output CANNOT be represented except by anything beyond perhaps a good high level description language with a compiler or translator that can take that description back to its binary original.

If the output of a Turing machine is the entire state at each step, the sequence itself would be impossible to replicate even though this requires an alternative definition of a TM to capture these hidden practical states.

Furthermore forgetting these issues, the question of whether a given self modifying code can be unrolled in P time or P space is hardly proven. It could be that removing all self modifying code causes an exponential blow up in program size. It's also the case that optimal Kolmogorov complexity might only be achievable via self modifying code. So the fact that it can theoretically be unrolled in all cases, says nothing about its impact on complexity, nor does it work in a practical environment which has micro instruction timing, cache issues, or even external clock type sensitivity which is measurable with modern processors very easily. It would be easy to make hand written assembly that detects if it is in it's original form verse a unwound form using several different techniques. Modern processors are highly complex state machines and effectively cannot be strictly modeled as TMs as there is no way to model an input tape that has external stimuli with such a primitive theoretical model. Immediately we must step into non deterministic or probabilistic TMs and NP or worse complexity
> 1 votes

---
Tags: computability, computation-models, turing-completeness, church-turing-thesis
---


title: Compute average case with best case

text:
# Question
Title: Compute average case with best case
is it correct to compute the average case time complexity of an algorithm by taking the mean of the best and worst cases ? My findings : for binary search, $\frac{\log (n) +1}{2}\in \Theta \left(\log (n )\right)\implies $ the average case is $\log (n).$

# Answer
> 0 votes
Not at all correct. For example for the naive Quicksort algorithm, anything close to the worst case is very, very, very rare. If the average time was between best and worst case, nobody in their right mind would use Quicksort.

# Answer
> 0 votes
For complexity analysis of some $T(n)$ function we usually consider it's minimum which is worst case, it's maximum, which is worst case, and average. By definition average is expected value of random variable, which means, that we have probability space structure on $T$ domain and, in discrete case, it is defined as

$$ET=\sum\limits\_{i} x\_i P(T^{-1}(x\_i))=\sum\limits\_{i} x\_i p\_i$$

where $x\_i$ are values obtained by $T$ and $P(T^{-1}(x\_i))=p\_i$ is expectation, probability of each $x\_i$. So, average is highly dependent on distribituon $(p\_1,\cdots,p\_n)$.

Now let's consider some examples.

1. Suppose $T$ is constant. Then, obviously min=max=average=$\frac{\text{min}+\text{max}}{2}$.
2. Suppose $T(i)=i$ for $i=\overline{1,n}$. Such complexity we have, for example, for comparisons in simple linear search. Assume, that each value is equally expected with $p\_i=P(T^{-1}(i))=\frac{1}{n}$. So called uniform distribution. For average we obtain

$$ET=\sum\limits\_{i=1}^{n}\frac{i}{n}=\frac{1}{n}\frac{n(n+1)}{2}=\frac{n+1}{2}=\frac{\text{min}+\text{max}}{2}=\frac{n}{2}+O(1)$$

Now let's consider that probability for value $x\_1=T(1)$ is same as for all other values together and is $\frac{1}{2}$. Then we have

$$ET=\frac{1}{2}+\sum\limits\_{i=2}^{n}\frac{i}{2n}=\frac{1}{2}+\frac{(n+1)(n-2)}{4n}=\frac{n}{4}+O(1)$$

3. If we consider $T(i)=i^2$ for $i=\overline{1,n}$, then even in uniform distribution case we have

$$ET=\sum\limits\_{i=1}^{n}\frac{i^2}{n}=\frac{1}{n}\frac{n(n+1)(2n+1)}{6} = \frac{n^2}{3}+O(1)$$

---
Tags: complexity-theory, time-complexity, data-structures, discrete-mathematics
---


# Question
Title: How to correctly negate a predicate bounded by some quantifiers?
this is a problem which was asked in GATE CS 2010.

**This is question statement:<br>Q:** Suppose the predicate F(x, y, t) is used to represent the statement that person x can fool person y at time t. which one of the statements below expresses best the meaning of the formula ∀x∃y∃t(¬F(x, y, t))?

**Options:**
**A:** Everyone can fool some person at some time.
**B:** No one can fool everyone all the time.
**C:** Everyone cannot fool some person all the time.
**D:** No one can fool some person at some time.

**According to my solution:**
If F(x): person x can fool person y at time t.
Then
$\forall$x $\exists$y $\exists$t ( ¬F( x, y, t ) )
is same as "Not all person x can fool some person y at some time t. which can be rewritten as "No one can fool some person at some time".
Hence Option D must be the correct one.
However I am wrong.

How to approach these type of problems.

# Answer
I'm not sure how general *this type of problem* is so I can't tell you if this will always be the best approach, but in this case you can move the negation to the top for more clarity.

$$\forall x\ \exists y\ \exists t\ \[\neg F(x,y,t)\]\equiv \forall x\ \exists y\ \[\neg\ \forall t F(x,y,t)\]\equiv \forall x\ \[\neg\ \forall y\ \forall t F(x,y,t)\]\equiv \neg \[\exists x\ \forall y\ \forall t F(x,y,t)\]$$

From this you should be able to find the correct answer, which is:

> B
> 2 votes

# Answer
F(x,y,t)⟹ person x can fool person y at time t.

For the sake of simplicity propagate negation sign outward by applying De Morgan's law.

∀x∃y∃t(¬F(x,y,t))≡¬∃x∀y∀t(F(x,y,t)) \[By applying De Morgan's law.\]

Now converting ¬∃x∀y∀t(F(x,y,t)) to English is simple.

¬∃x∀y∀t(F(x,y,t))⟹ There does not exist a person who can fool everyone all the time. Which means No one can fool everyone all the time.

So, option (B) is correct.
> 1 votes

---
Tags: logic, first-order-logic, propositional-logic, predicate-logic
---


# Question
Title: Is there a connection between the Undecidability Theorem and "software complexity"?
I was reading *Complexity: The Emerging Science at the Edge of Order and Chaos* and a certain passage got me really intrigued. When discussing Chris Langton's explorations of artificial life algorithms, the author paraphrases Langton stating the following about a certain set of evolutionary algorithms:

> This is the undecidability theorem, one of the deepest results of computer science: unless a computer program is utterly trivial, the fastest way to find out what it will do is to run it and see. There is no general purpose procedure that can scan the code and the input and give you the answer any faster than that. That’s why the old saw about computers only doing what their programmers tell them to do is both perfectly true and virtually irrelevant; any piece of code that’s complex enough to be interesting will always surprise its programmers. That’s why any decent software package has to be endlessly tested and debugged before it is released and that’s why the users always discover very quickly that the debugging was never quite perfect.

But I can't easily see how the undecidability theorem allows one to conclude that "unless a computer program is utterly trivial, the fastest way to find out what it will do is to run it and see".

Can such a connection be made formally, or was it more of an empirical observation?

# Answer
The author is here referring to the Halting problem, and possibly also Rice's theorem (without putting words into their mouths).

It says indeed that it's not possible to decide in advance whether a Turing machine will halt on any given input or not, thus it makes it impossible to decide in advance what the actual output of the machine will be.

This is the fundamental theorem of the field known as *recursion theory*, more known in these days as computability theory.

The computability theory comprises infinitely many complexity classes, which we are familiar with from complexity theory, but computability theory typically concerns itself with the complexity classes on the decidable/undecidable level: primitive recursive, through the computable class, to the recursively enumerable, and going infinitely beyond to the *highly undecidable problems* as can be studied via the arithmetical hierarchy.

There are many connections to our "normal" complexity theory, and indeed a very nice analog can be found from the arithmetical hierarchy to the polynomial hierarchy.
> 2 votes

---
Tags: complexity-theory, computability, undecidability, halting-problem, rice-theorem
---


# Question
Title: Proving that a certain language is regular using pumping lemma
Let $\Sigma = \\{a,b,c,\ldots,x,y,z\\}$ be the Latin alphabet, consisting of 26 letters. Consider the language $L$ of all words $\alpha$ over $\Sigma$ satisfying the following constraints:

* If $\alpha$ contains $a$ then it contains exactly $4$ many $a$s.
* If $\alpha$ contains $b$ then it contains exactly $8$ many $b$s.
* ...
* If $\alpha$ contains $\`$ then it contains exactly $2^{27}$ many $z$s.

How do I prove that $L$ is regular?

Note: I did research and I have found that we can use the pumping lemma.

# Answer
You cannot use the pumping lemma to show that a language is regular. The pumping lemma gives a property of regular languages: if $L$ is regular then $L$ can be "pumped". You can use this to show that $L$ is not regular: if $L$ cannot be pumped, then it is not regular. But you cannot use it to show that $L$ is regular: if $L$ can be pumped, it doesn't follow that $L$ is regular; moreover, there are examples of pumpable languages which are not regular. There are *extensions* of the pumping lemma which can be used to show that a language is regular, but they are not so useful in practice.

In your case, every word in $L$ contain $0$ or $4$ many $a$s, $0$ or $8$ many $b$s, and so on. In particular, it contains at most $4$ many $a$s, at most $8$ many $b$s, and so on. Therefore every word in $L$ has length at most $4+8+\cdots+2^{27}$. Consequently, $L$ is finite. Every finite language is regular.
> 5 votes

---
Tags: regular-languages
---


# Question
Title: Why is the common explanation to the halting problem an oversimplification?
So watching many youtube channels, the explanation to the impossibility of solving the halting problen involves assuming you can, doing the opposite, and feeding it back into itself to create a paradox.

What I don't get is why this is an (over)simplification. The logic seems to check out. What is the flaw in this reasoning?

# Answer
> 1 votes
It's basically correct, but it can be viewed as an oversimplification because that one sentence doesn't explain the details of how to feed it back into itself or why "feeding it back into itself" creates a paradox -- that requires additional explanation or justification.

---
Tags: halting-problem
---


# Question
Title: Proving equivalence of two substitutions by induction
I'm trying to prove the following reduction: $$ t\\{x:=u\\}\\{y:=v\\} = t\\{y:=v\\}\\{x:=u\\{y:=v\\}\\} $$ under the following assumptions:

1. $x \neq y$
2. $x$ is not a free variable of $v$ (in symbols, $x \notin \operatorname{fv}(v)$).

My idea is to do it by induction, but I'm a bit stuck with the base case. I would appreciate if someone can explain to me how to write such a proof. I'm including what I tried, which is wrong or incomplete.

*Base case*: $t = m$ is just a variable.

On the left side we have:

```
if m = x ⟹ u{y:=v} (if u=y then v else u)
else     ⟹ m{y:=v} (if m=y then v else m)

```

On the right side we have:

```
if m=y ⟹ v{x:=u{y:=v}} (if u=y then v{x:=v} else u{x:=u}
  so we get either (v=x ⟹ v else v) or (u=x ⟹ u else u)
else   ⟹ m{x:=u{y:=v}} (if m=y then m{x:=v} else m{x:=u}
  so we get either v or m

```

I understand we end up getting the same four branches, but is that considered really a proof? Is this the proper way to write such a proof and conclude the base case? Also, the given assumptions didn't help much here, so I think I'm missing the part where I need to use those assumptions...

I think once the base case is proven, we can do the following:

*Case $t = t\_1t\_2$:*

$$t\\{x:=u\\}\\{y:=v\\} \Longrightarrow t\_1t\_2\\{x:=u\\}\\{y:=v\\} \Longrightarrow \\ t\_1\\{x:=u\\}\\{y:=v\\} t\_2\\{x:=u\\}\\{y:=v\\},$$ and we have just proven in the base case that $t\_1\\{x:=u\\}\\{y:=v\\} = t\_1\\{y:=v\\}\\{x:=u\\{y:=v\\}\\}$ and $t\_2\\{x:=u\\}\\{y:=v\\} = t\_2\\{y:=v\\}\\{x:=u\\{y:=v\\}\\}$, so \begin{align} &t\_1\\{x:=u\\}\\{y:=v\\} t\_2\\{x:=u\\}\\{y:=v\\} \\ =& t\_1\\{y:=v\\}\\{x:=u\\{y:=v\\}\\} t\_2\\{y:=v\\}\\{x:=u\\{y:=v\\}\\} \\ = &t\_1t\_2\\{x:=u\\}\\{y:=v\\} \\ = &t\_1t\_2\\{y:=v\\}\\{x:=u\\{y:=v\\}\\}. \end{align}

Now only case left is $t= \lambda m . t$. So we have $(\lambda m . t)\\{x:=u\\}\\{y:=v\\}$, which can be directly re-written as $\lambda m . t\\{x:=u\\}\\{y:=v\\}$, which is the base case again...

Could someone please help me finish this proof correctly and explain to me the right way to do it?

# Answer
First, let us show that the two assumptions are necessary. Here is an example showing what goes wrong when $x = y$. Take $t = x$, $u = 1$, $v = 2$. We have $$ x\\{x := 1\\}\\{x := 2\\} = 1\\{x := 2\\} = 1, $$ whereas $$ x\\{x := 2\\}\\{x := 1\\{x := 2\\}\\} = 2\\{x := 1\\} = 2. $$

Next, here is an example showing what goes wrong when $x$ is not free in $v$. Take $t = y$, $x = 1$, $y = x$. We have $$ y \\{x := 1\\}\\{y := x\\} = y\\{y := x\\} = x, $$ whereas $$ y \\{y := x\\}\\{x := 1\\{y := x\\}\\} = x\\{x := 1\\} = 1. $$

Now let's do the base case more carefully. The term $t$ is just a variable. We have to consider three possibilities: $t=x$, $t=y$, $t \neq x,y$.

If $t=x$ then $t\\{x := u\\} = u$, and so the left-hand side is $u\\{y := v\\} = u\\{y := v\\}$. On the other hand, $t\\{y := v\\} = x$ (since $x \neq y$), and so the right-hand side is $x\\{x := u\\{y := v\\}\\} = u \\{y := v\\}$.

If $t=y$ then $t\\{x := u\\} = y$ (since $y \neq x$), and so the left-hand side is $y\\{y := v\\} = v$. On the other hand, $t\\{y := v\\} = v$, and so the right-hand side is $v\\{ x:= u\\{y := v\\} \\} = v$, since $x$ doesn't appear freely in $v$.

Finally, if $t \neq x,y$ then both sides are just equal to $t$, since the substitutions have no effect.

Next, the rest of the proof. The proof for function application is essentially as you wrote it. Let us denote the left-hand side by $L(t)$ and the right-hand side by $R(t)$. If $t = t\_1t\_2$ then $$ L(t) = L(t\_1) L(t\_2) \stackrel{(\ast)}= R(t\_1) R(t\_2) = R(t), $$ where $(\ast)$ is due to the induction hypothesis.

Finally, we need to handle abstraction. Let $t = \lambda m.s$. Applying $\alpha$-conversion, we can assume without loss of generality that $m \neq x,y$. This implies that $$ L(t) = \lambda m.L(s) = \lambda m.R(s) = R(t). $$ To see why $\alpha$-conversion is necessary, try doing the proof when $m=x$ or $m=y$. The case $m=x$ works out fine, but you will encounter a problem when $m=y$.
> 4 votes

---
Tags: logic, proof-techniques, lambda-calculus, semantics, term-rewriting
---


# Question
Title: Unrecognizability of functional variant of halting problem
Let $L\_0 = \\{ \langle M, w, 0 \rangle \mid M \text{ halts on } w\\}$ and $L\_1 = \\{\langle M, w, 1\rangle \mid M \text{ does not halt on } w\\}$. In $\langle M,w,i \rangle$, the $i$ indicates a specific bit such as $0$ for language $L\_0$ and $1$ for language $L\_1$.

I want to prove that $L = L\_0 \cup L\_1$ is unrecognizable and so is $\overline{L}$.

I think: the halting problem $\\{\langle M,x \rangle \mid M \text{ halts on input } x \\}$ is recognizable, that is, given a machine $M$ and a string $w$, I can always get acceptance if $M$ stops on $w$ by simply running it.

Assume that $L\_0$ and $L\_1$ are recognizable, that is, there are machines $M\_0$ and $M\_1$ such that $M\_0$ accepts $x \in L\_0$ and halts, $M\_1$ accepts $x \in L\_1$ and halts. Then to recognize $x \in L\_0 \cup L\_1$, we can have a hypothetical $M\_\cup$ that can recognize (not decide) $L\_0 \cup L\_1$:

* we can run $\langle M, w, 0 \rangle \in L\_0$ on $M\_0$
* and $ \langle M, w, 1 \rangle \in L\_1$ on $M\_1$

So:

* If $M\_0$ stops we know $M$ halts on $w$ and
* if $M\_1$ stops we know $M$ does not halt on $w$

(Note that any $x \not \in L\_0 \cup L\_1$ will lead to divergence on these two machines. That’s why $M\_\cup$ can only recognize $L\_0 \cup L\_1$ and cannot decide.)

Thus we have solved the halting problem: for any $M$ and $w$, $M\_\cup$ will accept and halt for both

* $M$ halts on $w$
* $M$ does not halt on $w$

This is a contradiction (halting problem is undecidable) and so both $M\_0$ and $M\_1$ cannot exist simultaneously. This proves that $L = L\_0 \cup L\_1$ is not recognizable.

For the $\overline{L}$ case: $\overline{L} = \overline{L\_0} \cap \overline{L\_1}$. As stated previously, $L\_0$ is recognizable and $L\_1$ is not recognizable (“no Turing machine can recognize all Turing machines that never halt”: Corollary 2 here).

* $\overline{L\_0}$ is not recognizable
* $\overline{L\_1}$ is recognizable
* $\implies \overline{L}$ is not recognizable

Is this a valid chain of arguments for this proof?

# Answer
> 1 votes
A Turing machine $T$ decides the halting problem if on input $\langle M,w \rangle$:

* If $M$ halts on $w$, then $T$ halts and outputs "Yes".
* If $M$ does not halt on $w$, then $T$ halts and outputs "No".

In order to show that $L$ is not recognizable, you assume that $L$ is recognizable, and use that to construct a Turing machine $T$ which decides the halting problem. This is not quite what you are doing:

* You are assuming that $L\_0,L\_1$ are recognizable, but you don't explain how this follows from $L$ being recognizable.
* You don't explain why $M\_{\cup}$ always halts. This is only the case if you run $M\_0$ and $M\_1$ in parallel, and halt whenever one of them halts.
* You state that $M\_{\cup}$ always accepts and halts whether $M$ halts on $w$ or not. However, such a machine is easy to construct: all you need to do is to immediately halt, without even reading the input. What we need is that $M\_{\cup}$ halts with a different answer depending on whether $M$ halts on $w$ or not.

---

Moving forward, for $\overline{L}$, you express $\overline{L}$ as the intersection of a non-recognizable language and a recognizable language, and conclude that $\overline{L}$ is not recognizable. Unfortunately, this step is invalid. For example, the empty language is the intersection of a non-recognizable language of your choice and the empty language, which is recognizable; yet the empty language is recognizable.

Instead, you need an argument very similar to the one you use for $L$ itself.

---
Tags: turing-machines
---


title: Binary cross Entropy derivative?

text:
# Question
Title: Binary cross Entropy derivative?
I am just learning backpropagation algorithm for NN and currently I am stuck with the right derivative of *Binary Cross Entropy* as loss function.

Here it is:

```
def binary_crossentropy(y, y_out):
    return -1 * (y * np.log(y_out) + (1-y)*np.log(1-y_out))

def binary_crossentropy_dev(y, y_out):
    return binary_crossentropy(y, y_out) * (1 - binary_crossentropy(y, y_out))

def binary_crossentropy_dev2(y, y_out):
    return (y_out - y)/ (y_out * (1-y_out))

```

But when comparing both derivative above with real numbers, their results are differenct altough they should be the same. What am I doing wrong with the above equations? Thank you!

# Answer
Here is the definition of cross-entropy for Bernoulli random variables $\operatorname{Ber}(p),\operatorname{Ber}(q)$, taken from Wikipedia: $$ H(p,q) = p \log \frac{1}{q} + (1-p) \log \frac{1}{1-q}. $$ This is exactly what your first function computes.

The partial derivative of this function with respect to $p$ is $$ \frac{\partial H(p,q)}{\partial p} = \log \frac{1}{q} - \log \frac{1}{1-q} = \log \frac{1-q}{q}. $$ The partial derivative of this function with respect to $q$ is $$ \frac{\partial H(p,q)}{\partial q} = -\frac{p}{q} + \frac{1-p}{1-q} = \frac{(1-p)q-p(1-q)}{q(1-q)} = \frac{q-p}{q(1-q)}. $$ This is exactly what your third function computes.

I'm not sure what your second function computes. Also, there is no reason to expect that the partial derivative with respect to one variable will be the same as the partial derivative with respect to another variable.
> 1 votes

---
Tags: neural-networks, entropy, derivation
---


# Question
Title: Why is the Kth Largest Element solution using a MinHeap O(N lgK) in complexity?
This is a rather well known solution to the $k$-th order statistic problem which requires us to find the $k$-th largest number in an unsorted array with $n$ elements where $1 \leq k \leq n$:

```
public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>();

        for (int num: nums) {
            heap.add(num);

            if (heap.size() > k) {
                heap.remove();
            }
        }

        return heap.remove();
    }

```

A brief summary of this approach is that we maintain a min heap and keep polling from this heap each time its size exceeds $k$. This way, our final heap will contain $k$ elements, and these $k$ elements are guaranteed to be last $k$ elements in the sorted array (since we have been polling minimums). Within these last $k$ elements, the minimum element is guaranteed to be the $k$-th largest so we extract the min and return that as a result.

What I don't particularly understand is why this problem is $\mathcal{O}(n \lg{(k)})$. For instance, after $\mathcal{O}(n)$ creation of the heap, we do an extraction of the minimum $n - k $ times, which would require sifting up in the heap $n - k$ times and hence, shouldn't this solution be $\mathcal{O}(n \lg{(n - k)})$?

Thanks!

# Answer
The maximum number of elements in the heap at any given time is upper bounded by $k+1$.

Since each insertion or deletion from an heap requires $O(\log \eta)$ time where $\eta$ is the number of elements in the heap at the time of the operation, and $\eta \le k+1$, we know that each heap operation can be performed in time $O(\log (k+1) ) = O( \log k )$.

How many heap operations does the algorithm perform? Each element is inserted once, so there are $n$ insertions. In addition all but the largest $k-1$ elements are extracted. This yields a total of $n + (n-(k-1)) = 2n-k+1 = O(n)$ operations.

By multiplying the number of operations with our upper bound on the time required by each operation of $O(\log k)$ we obtain an overall time complexity of $O(n \log k)$.
> 0 votes

---
Tags: time-complexity
---


# Question
Title: Comparison of $(\log^* n)!$ and $(n\log n)^b$
How can I compare $(\log^\*n)!$ with $(n\log n)^b$? I know that $n^b\<n!$.

# Answer
For sufficiently large values of $n$, and $b\>0$:

$$ ( \log^\*n )! \< ( \log \log n )! \< (\log \log n)^{\log \log n} = 2^{(\log\log n) \log \log \log n} \in o(2^{b \log n}) \subset o( (n \log n)^b ). $$
> 2 votes

---
Tags: asymptotics
---


# Question
Title: If $L$ is regular then $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free
I have found a problem about proving whether $L^{|2|}=\\{w\_1w\_2 \mid w\_1,w\_2\in L, |w\_1|=|w\_2|\\}$ is context-free or not, knowing that $L$ is regular

So far I know that:

* There are examples where $L$ is regular and $L^{|2|}$ is regular (for example $L=\\{a,b\\}$)
* There are examples where $L$ is regular and $L^{|2|}$ is not (for example $L=\\{w \mid w=a^N \text{ or } w= b^N\ , N\ge0\\}$)

But I am not sure how to prove that it's context-free regardless of which regular language I use. I have found similar problems with the same language without imposing restrictions on which words to use, but I am not sure if those apply to this one.

# Answer
> 2 votes
Let $\mathcal{A}$ be a DFA for $L$. A direction is to consider a PDA $\mathcal{B}$ for $L^{|2|}$ that is defined on top of the product of $\mathcal{A}$ with itself, that is, the state-space of $\mathcal{B}$ is $(Q\_{\mathcal{A}} \cup \\{ null\\})\times Q\_\mathcal{A}$, where $null$ is a special state that is not in $Q\_{\mathcal{A}}$, to be explained below. The PDA $\mathcal{B}$ operates as follows. The initial state of $\mathcal{B}$ is $\langle q^{\mathcal{A}}\_0, q^{\mathcal{A}}\_0\rangle$, that is, both coordinates are initialized to the initial state of $\mathcal{A}$. The PDA $\mathcal{B}$ modifies only the left coordinate or the right coordinate at a time. $\mathcal{B}$ starts by simulating the run of $\mathcal{A}$ on the left coordinate while pushing input letters into the stack. When $\mathcal{B}$ reaches an accepting state in the left coordinate, it guesses to do one of the following:

1- it guesses that it just finished reading the prefix $w\_1$, so it modifies the left coordinate to $null$, and operates from this point on only on the right coordinate that takes care of the suffix $w\_2$.

2- it guesses that we did not finish reading the prefix $w\_1$, and continues to modify the left coordinate.

If at some point $\mathcal{B}$ guess option 1 above, then $\mathcal{B}$ runs $\mathcal{A}$ on the right coordinate, and at the same time checks whether $|w\_1| = |w\_2|$ which can be done by popping letters from the stack for each input letter that we read. For example, if at some point the stack becomes empty, and we did not finish reading the input, this means that in the current guess $|w\_2| \> |w\_1|$, and thus we move to a rejecting sink. $\mathcal{B}$ only accepts if the stack is empty and the 2nd coordinate is an accepting state of $\mathcal{A}$. To define $\mathcal{B}$ formally, you might need an additional binary coordinate (or you can use the left coordinate) to indicate whether the stack just became empty. Then, the accepting states of $\mathcal{B}$ are those having $null$ in the left coordinate, an accepting state in the right coordinate, and the additional coordinate specifies that the stack just became empty.

I only gave the general idea, I leave the details to you.

**Edit:** note that you can easily modify the above construction so that the number of states of $\mathcal{B}$ is linear in $|Q\_{\mathcal{A}}|$. To see why, note that both the first and the second simulation can be done on the same coordinate, you only need a bit to remember which simulation we're doing now.

# Answer
> 4 votes
Let $\Sigma' = \\{\sigma' : \sigma \in \Sigma\\}$ be a tagged version of the alphabet of $\Sigma$. Let $L'$ be a version of $L$ obtained by tagging all letters. Let $h\colon \Sigma \cup \Sigma' \to \Sigma$ be a homomorphism which removes tags. Then $$ L^{|2|} = h(LL' \cap \\{xy : x \in \Sigma^n, y \in \Sigma^{\prime n} \text{ for some } n\\}). $$ Standard closure properties of context-free languages imply that $L^{|2|}$ is context-free.

# Answer
> 2 votes
Let $L$ be a regular language, then $L$ has both a left linear grammar and a right linear grammar.

The right linear grammar $G\_R$ has axiom $S\_L$ and productions of the form $A\to\_R aB$ or $A\to\_R\varepsilon$, and the left linear grammar has axiom $S\_L$ and productions of the form $P\to\_L Qa$ or $P\to\_L\varepsilon$. Note that the left linear grammar is deriving its strings 'backwards', so from right to left. (We can directly construct such grammars from a finite automaton for $L$.)

Now we can construct a context-free grammar $G$ (actually a linear grammar) that simulates two derivations in parallel, and by construction they are of the same length. The variables of the CFG $G$ are pairs of variables of $G\_R$ and $G\_L$. I will write them as $\langle AP\rangle$, buth you might prefer $N\_{AP}$.

* axiom $\langle S\_RS\_L\rangle$
* productions $\langle AP\rangle \to a\\,\langle BQ\rangle\\, b$, if $A\to\_R aB$ and $P\to\_L Qb$
* productions $\langle AP\rangle \to \varepsilon$, if $A\to\_R \varepsilon$ and $P\to\_L \varepsilon$

# Answer
> 1 votes
Here is a sketch of an NPDA for $L^{|2|}$ given a regular language $L$.

If $L$ is regular then it has a DFA $M$. We assume for simplicity that $M$ has one final state only. Create two NPDA from $M$. One is $M\_{push}$ which is $M$ but with a stack such that every time it reads an input it pushes a symbol, say $X$. The other NPDA is $M\_{pop}$ that pops the stack each time it reads an input. By construction, $M\_{pop}$ will not accept any input since initially the stack is empty. However, it will be useful in combination with $M\_{push}$ if they work in sequence, which we now take advantage to contruct the NPDA for $L^{|2|}$.

We now construct NPDA $M'$ for $L^{|2|}$. From the final state of $M\_{push}$ create a transition that reads no input and does not push nor pop going to the start state of $M\_{pop}$. Finally, make the final state of $M\_{push}$ an ordinary state.

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


# Question
Title: Efficient Algorithms for Complex Networks
Most standard works on random graphs focus on $G\_{n,p}$ and random regular graphs. However, such models are far from a good abstraction to describe the types of networks that one typically encounters in the real world.

There are several simple models that mimic the behavior of real-world graphs, sometimes called Complex Networks.

There are many graph problems that become easier in the setting of $G\_{n,p}$, such as finding a Hamiltonian path, finding a perfect matching, etc. I am sure that similar work has been done for random complex networks, but I haven't been able to find a good book or survey paper on the subject. I must be using the wrong terminology.

I would be grateful if someone could point me towards something like that, or tell me what the subject of efficient algorithms for complex networks is called in the literature.

# Answer
> 1 votes
There are currently serious efforts devoted to **algorithms taking into account usual properties of complex networks**, either in their design (use these properties to be efficient) or in their analysis (show that, if the input graph has these properties, then the algorithm has low complexity).

Since most complex networks met in practice are *sparse*, let me first say that any complexity expressed in terms of the number of edges (instead of the squared number of vertices) is of interest in this context. But I do understand that you actually have more advanced complex network properties and complexity analysis in mind.

My 2006 paper about triangle counting and listing provides a good illustration, I think. There, I used the fact that most complex networks met in practice have very *heterogeneous degrees*. I proposed a very simple algorithm makes a distinction between low- and high-degree vertices, and proved its algorithmic complexity as a function of the graph degree distribution.

Many such examples exist in the literature. For instance, the arboricity and core value have been used to enumerate $k$-cliques. However I am not aware on any survey devoted to them.

---
Tags: algorithms, random-graphs
---


# Question
Title: Proof that $P\subseteq NP$ without nondeterministic TM
I know the proof that using nondeterministic TM, but as I understood there is another proof without nondeterministic TM. If you answer please write with as much details as you can.

# Answer
> 7 votes
The first definition you are referring to is probably the one that defines $\mathsf{NP}$ as the set of problems $\Pi$ for which there exist a non-deterministic poly-time Turing machine that decides $\Pi$. Since any problem $\Pi \in \mathsf{P}$ can be decided by a deterministic poly-time Turing machine $T$, and $T$ itself is also a non-deterministic Turing machine, it follows that $\Pi \in \mathsf{NP}$, i.e., $\mathsf{P} \subseteq \mathsf{NP}$.

However $\mathsf{NP}$ can be equivalently defined as the set of decision problems $\Pi$ for which there exists a poly-time *verifier* (a Turing machine) $V$ and a polynomial $p$ such that if $x \in \\{0,1\\}^\*$ is an instance of $\Pi$, then there exists a *certificate* $c \in \\{0,1\\}^\*$ of length $|c| \le p(|x|)$ such that $V(x,c)$ accepts if and only if $x$ is a yes-instance for $\Pi$.

Using this definition every problem $\Pi \in \mathsf{P}$ is also in $\mathsf{NP}$, since it suffices to choose $p(|x|)=0$, $c(x)=\varepsilon$ (where $\varepsilon$ denotes the empty word), and $V(x, c)$ as the Turing machine that simulates any poly-time decider $T$ for $\Pi$ and accepts iff $T(x)$ accepts.

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


# Question
Title: Worst case analysis of $100n + 5$ for different $n$
For the function $f(n) = 100n + 5$, what is the asymptotic complexity of $f(n)$ in terms of Big O notation. I guess it is $O(n)$, but how can I prove it ?

# Answer
All you need is to write the definition of Big O notion:

> f(n) = O(n) if and only if there is a `c` and an `m` such that for all n :
> 100n+5 \> cn for all n \> m

If you can find such `m` and `c` then you have proven `f(n) = O(n)`. `c` and `m` can be 10 and 11 (as an example).
> -1 votes

# Answer
Big-$O$ is the set of functions $$O(f)=\\{g\colon \exists C\>0, \exists N \in \mathbb{N}, \forall n \> N, g(n) \leqslant Cf(n) \\}$$ So we can write $100n+5 \leqslant 105\cdot n$, taking $C=105, N=1$, and we obtain $$100n+5 \in O(n)$$
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Is object oriented programming considered to be a declarative programming approach?
Is object oriented programming considered to be a declarative programming approach?

On Wikipedia, it is said that OOP tries to extend the imperative programming paradigm to a somewhat declarative programming approach, but **what precisely makes OOP imperative or declarative?**

# Answer
**When you write an OO code, you describe object features** (attributes, properties, methods) and implement them. This may be seen as declarative: you do not have an imperative approach giving the sequence of operations to reach a given goal; you have a declarative approach *describing* features of objects, in a sense characterizing them.

To be more precise, let me take an example. When one says that an image has a filtered version, a blurred version, etc, this may be seen as declarative; these are features of any image. When one implements a procedure to filter or blur an image, then this is imperative: the code is thought of as a sequence of operations aiming at transforming an image, not a description of what the transformed image is.

I am not an expert, though, so I hope someone will correct this if needed.
> 1 votes

---
Tags: object-oriented, programming-paradigms, imperative-programming
---


# Question
Title: General method behind converting recursive inorder, preorder and postorder traversals of a binary tree to a non-recursive one?
I am reading both recursive and non-recursive using stack methods to implement inorder, preorder and postorder traversal of a binary tree at https://en.wikipedia.org/wiki/Tree\_traversal#Depth-first\_search\_2, which I also copied below.

What confuses me most is that

* I find the non-recursive implementations using stacks are not easy to understand.
* It also seems to me that the three non-recursive implementations are ad hoc on each own, and I can't find if there is a way to unify their creations.

Can they be reformuated and/or created from the recursive implementations in some unified way, so that I can write them out by just looking at the recursive implementations?

Since a compiler can implement recursions using stacks, I believe it is possible to do that.

One reply I saw

> Usually, I replace a recursive algorithm by an iterative algorithm by pushing the parameters that would normally be passed to the recursive function onto a stack. In fact, you are replacing the program stack by one of your own.
>
> ```
> Stack<Object> stack;
> stack.push(first_object);
> while( !stack.isEmpty() ) {
>    // Do something
>    my_object = stack.pop();
>
>   // Push other objects on the stack.
>
> }
>
> ```
>
> Note: if you have more than one recursive call inside and you want to preserve the order of the calls, you have to add them in the reverse order to the stack:
>
> ```
> foo(first);
> foo(second);
>
> ```
>
> has to be replaced by
>
> ```
> stack.push(second);
> stack.push(first);
>
> ```

In the idea of the reply, the non-recursive implementation of preorder is easier to understand than the non-recursive implemenations of the other two. The non-recursive implemenations of the other two don't seem to follow the idea at least closely, and can they be written to follow the idea closely?

Thanks.

---

Note the implementations from Wikipedia are

> **Pre-order**
>
> ```
> preorder(node)
>   if (node = null)
>     return
>   visit(node)
>   preorder(node.left)
>   preorder(node.right)
>
> iterativePreorder(node)
>   if (node = null)
>     return
>   s ← empty stack
>   s.push(node)
>   while (not s.isEmpty())
>     node ← s.pop()
>     visit(node)
>     if (node.right ≠ null)
>       s.push(node.right)
>     if (node.left ≠ null)
>       s.push(node.left)
>
> ```
>
> **In-order**
>
> ```
> inorder(node)
>   if (node = null)
>     return
>   inorder(node.left)
>   visit(node)
>   inorder(node.right)
>
> iterativeInorder(node)
>   s ← empty stack
>   while (not s.isEmpty() or node ≠ null)
>     if (node ≠ null)
>       s.push(node)
>       node ← node.left
>     else
>       node ← s.pop()
>       visit(node)
>       node ← node.right
>
> ```
>
> **Post-order**
>
> ```
> postorder(node)
>   if (node = null)
>     return
>   postorder(node.left)
>   postorder(node.right)
>   visit(node)
>
> iterativePostorder(node)
>   s ← empty stack
>   lastNodeVisited ← null
>   while (not s.isEmpty() or node ≠ null)
>     if (node ≠ null)
>       s.push(node)
>       node ← node.left
>     else
>       peekNode ← s.peek()
>       // if right child exists and traversing node
>       // from left child, then move right
>       if (peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right)
>         node ← peekNode.right
>       else
>         visit(peekNode)
>         lastNodeVisited ← s.pop()
>
> ```

# Answer
> 3 votes
> Can they be reformuated and/or created from the recursive implementations in some unified way, so that I can write them out by just looking at the recursive implementations?

Yes, they can be reformulated in a unified way.

We take the `<pre/in/post>_order` recursive calls together with the `visit` procedure call, reverse them and push the corresponding nodes on the stack `s`, *marking* each node with its purpose: `TRAVERSE` or `VISIT`. I think the examples below explain the idea better.

## Preorder traversal

So, `iterativePreorder` can be reformulated as

```
iterativePreorder(node)
  s ← empty stack
  s.push(<node, TRAVERSE>)

  while (not s.isEmpty())
    <node, mark> ← s.pop()
    if node = null
      continue
    if mark = TRAVERSE
      s.push(<node.right, TRAVERSE>)
      s.push(<node.left, TRAVERSE>)
      s.push(<node, VISIT>)
    else
      visit(node)

```

It's easy to see the above pseudocode can be transformed into the `iterativePreorder` procedure provided in the question by

* eliminating two consecutive `push`/ `pop` operations on the same node;
* not pushing `null`-nodes on the stack.

## In-order traversal

Skipping the boilerplate code, we get:

```
iterativeInorder(node)
...
    if mark = TRAVERSE
      s.push(<node.right, TRAVERSE>)
      s.push(<node, VISIT>)
      s.push(<node.left, TRAVERSE>)
...

```

## Postorder traversal

```
iterativePostorder(node)
...
    if mark = TRAVERSE
      s.push(<node, VISIT>)
      s.push(<node.right, TRAVERSE>)
      s.push(<node.left, TRAVERSE>)
...

```

The `iterativeInorder` and `iterativePostorder` procedures cited in the question don't look like the above code because they make use of the traversal patterns arising in those cases. Like the fact that under *in-order* traversal we go straight to the leftmost leaf of the input tree, visit it, go one level up and do the same thing for the right subtree of the current node, etc.

# Answer
> 1 votes
"I find the non-recursive implementations using stacks are not easy to understand."

* One reason the complexity comes is due to "simulating" our own call-stack, which was done by compiler for the recursive method. The non-recursive variant may also include some optimization in addition to implementing what the recursive method does.

"It also seems to me that the three non-recursive implementations are ad hoc on each own, and I can't find if there is a way to unify their creations."

* There can be a unified way, which applies to all the 3 traversals. Though, as said above, we may apply optimizations to individual methods and they may start looking non-similar.

"Can they be reformulated and/or created from the recursive implementations in some unified way?"

* We can begin by knowing that we need to implement the recursive calls ourselves managing our own stack (this is done by compiler/program-stack automatically for recursive methods). The elements of our stack will need to track nodes and their state. The state will tell us what is the next task to do for that node, and any local-variables to remember. For example, which step of the recursive-method is to be executed next for that node. We can then have a loop which keeps on handling the topmost element of this stack based on its state, and also pushes/pops on this stack.

Take example of postorder traversal. We mark the locations where a call would "resume" (fresh initial call, or after a recursive call returns). Below these are marked as "RP 0", "RP 1" etc ("Resume Point").

```
void post(node *x)
{
  /* RP 0 */
  if(x->lc) post(x->lc);
  /* RP 1 */
  if(x->rc) post(x->rc);
  /* RP 2 */
  process(x);
}

```

Its iterative variant, which also includes an optimization as mentioned below:

```
void post_i(node *root)
{
  node *stack[1000];
  int top;
  node *popped;

  stack[0] = root;
  top = 0;
  popped = NULL;

#define POPPED_A_CHILD() \
  (popped && (popped == curr->lc || popped == curr->rc))

  while(top >= 0)
  {
    node *curr = stack[top];

    if(!POPPED_A_CHILD())
    {
      /* type (x: 0) */
      if(curr->rc || curr->lc)
      {
        if(curr->rc) stack[++top] = curr->rc;

        if(curr->lc) stack[++top] = curr->lc;

        popped = NULL;
        continue;
      }
    }

    /* type (x: 2) */
    process(curr);
    top--;
    popped = curr;
  }
}

```

The code comments with `(x: 0)` and `(x: 2)` correspond to the "RP 0" and "RP 2" resume points in the recursive method.

Optimization: By pushing both the `lc` and `rc` pointers together, we have removed the need of keeping the `post(x)` invocation at resume-point 1 while the `post(x->lc)` completes its execution. That is, we could directly shift the node to "RP 2", bypassing "RP 1". So, there is no node kept on stack at "RP 1" stage.

Optimization: The `POPPED_A_CHILD` macro helps us deduce one of the two resume-points ("RP 0", or "RP 2"). Thus we have avoided the need to store, along with each node on stack, its state/resume-point.

You can read in detail about this general method applicable to all 3 traversals, and also individual optimizations possible, in this article written by me.

---
Tags: algorithms, binary-trees, recursion, graph-traversal
---


# Question
Title: Where to put the state in a two-stack push down automaton?
theoretically, the state is between the two kleene-stars of the work-alphabet

```
gamma* q gamma*

```

where q is the current state and each `gamma*` is the content of one of both stacks. But where is "the middle" with the state? Regarding the one tape of the classical Turing Machine it is obvious.

Yours, von Spotz

# Answer
A *configuration* of a TM is usually defined as $uq\sigma v$, where $u\sigma v$ is the tape's content up to a cell from which there are only blanks, $q$ is the current state, and the head of the machine points at the letter $\sigma$. So the *place* of the state $q$ in the configuration $uq\sigma v$ is there simply to indicate at which letter the head points. Generally, a configuration holds a snapshot of the model during its run, including all information that is relevant to carry out the computation one step at a time.

Now consider a two-stack PDA $\mathcal{A}$, and think how to defined a configuration of it. Here, unlike TMs, we always point (in each stack) at the top of the stack, and therefore an indication to the stacks contents is sufficient - storing where the heads point does not add valuable information to help us compute the next configuration, given the current one. Specifically, the necessary information a configuration of $\mathcal{A}$ needs to hold are:

1- the content of the two stacks.

2- the current state.

3- the input left to be read.

So, we can define a configuration as a word of the form $ u q v \\# w$, where $u$ is the content of the first stack, $v$ is the content of the second stack, $q$ is the current state, $w$ is the input left to be read, and $\\#$ is a special charecter to indicate the end of $v$ and the beginning of $w$. Please note that the fact that $q$ is between $u$ and $v$ is not crucial. We could have defined a configuration of $\mathcal{A}$ as $qu\\#v\\#w$, and that makes no difference as long as we agree on which definition we stick. Anyway, I think the later definition is closer to being standard.
> 2 votes

---
Tags: turing-machines, pushdown-automata
---


# Question
Title: Find number of candidate keys given non-trivial functional dependency X->Y, where X is some set of attributes and Y is some prime attribute
In a relation R, if X is some set of attributes and Y is some prime attribute such that X uniquely determines Y is a non-trivial FD. Then is it true that R has **at least two** candidate keys?

---

For instance, take the relation schema *R(Class\_Id, Course\_Number, Instructor\_Name, Text)*. *{Class\_Id, Course\_number}* is a candidate key. This makes *Course\_Number* a prime attribute.

The following functional dependency holds on R:

* *{Instructor\_Name, Text}* uniquely determines *{Course\_Number}*

How to determine if another candidate key exist or not?

---

**EDIT**: A Relational table

```
Class_Id | Course_Number | Instructor_Name | Text

    2             b            Jodi           E
    3             c            Jack           N
    2             c            Jack           N
    4             b            Peny           E
    5             e            Jodi           N

```

# Answer
`X -> Y` non-trivial means that `X` does not include `Y`. Since `Y` is a prime attribute, we know that there is at least a candidate key that include it. Let's call this key `K1`.

Now we have two cases: either `X` is a superkey, or not.

If `X` is a superkey, then it contains at least a candidate key `K`. We can easily convince that `K ≠ K1`, since it differ from `K1` by at least one attribute.

So in this case in the relation there are at least two different candidate keys, `K` and `K1`.

Now suppose that `X` is *not* a superkey, and consider `X ∪ (K1 - {Y})`. This is surely a superkey, since it determines `K1`, which determines all the attributes. This superkey does not contains `Y`, but contains at least a candidate key `K'`, so again we have at least two different candidate keys, `K'` and `K1`.

**Edit**

Let's see in a more formal way why `X ∪ (K1 - {Y})` is a superkey.

A superkey is a set of attributes that determines all the attributes of the relation, and we can check this property by computing its closure and see if it contains all the attributes of the relation (let's call them `T`).

Since `K1` is a candidate key, we know that:

```
(1) K1 -> T

```

we also know:

```
(2) X -> Y
(3) Y ∈ K1

```

So we can calculate the closure of `X ∪ (K1 - {Y})` in this way:

```
(4) (X ∪ (K1 - {Y}))+ = X ∪ (K1 - {Y})
(5) (X ∪ (K1 - {Y}))+ = X ∪ (K1 - {Y}) ∪ Y = X ∪ K1  by (4) and (2)
(6) (X ∪ (K1 - {Y}))+ = X ∪ K1 ∪ T = T by (5) and (1)

```

so we can conclude that `(X ∪ (K1 - {Y}))+` contains `T`, and, consequently, that `(X ∪ (K1 - {Y}))` is a superkey.
> 1 votes

---
Tags: database-theory, databases, functional-dependencies
---


# Question
Title: Relaxation possibilities of the lower bound worst case sorting algorithms without quantum computation
The sorting algorithms (merge-sort, quicksort...) are tought to have an absolutely hard lower bound which can not be outperformed by computation alone and this bound is $n\*log\_{2}(n)$,

The reason for this bound is that those algorithms are using the division by two devide and conquer method and as such they generate a binary tree that begins at a root and from there on branches two times from each node until it reaches the bottom to produce exactly $n$ leaves at the bottom level.

Since it is a binary tree, it has exactly $log\_{2}(n)$ levels from the root down to the leaves and as such it costs $log\_{2}(n)$ "computational decisions" to generate the tree and $n$ decisions to walk over all leaves, so $n\*log\_{2}(n)$ looks absolutely valid at first.

I don't argue about the factor $n$ before the $log\_{2}(n)$, what I argue about is, why is it everywhere such a strict advocating consensus about to always use $log\_{2}(n)$ in computer science.

Imagine for example instead if I don't use the binary devide&conquer method, but if I adress the indices of the list which are prime numbers, using the values of those indices as representational values to compute the differences of the indices between the primes. The resulted tree structure from such an algorithm will have many more branches than two at most of the nodes and the generated tree size will be much much lower.

An computational approximation of an list with 1000000000 and the assumption of having 10 splits instead of two would result in 270 times less computational decisions when the $log\_{10}(n)$ insead of the $log\_{2}(n)$ would be used and I'm quite confident that this can be relaxed to an even much smaller tree in general, if I'm not oversimplifying it at least.

# Answer
Fist of all the $\Omega(n \log n)$ lower bound only applies to comparison-based algorithms, that is only to algorithm that can only obtain information on the relative orders of two input elements by pairwise comparisons.

They do not have to be divide and conquer algorithms and they do not have to generate any tree. The lower bound simply follows from the fact that there are $n!$ possible permutations of the input elements and any correct algorithm must be able to output all of them (given the inverse permutation as its input). This means that the number of branches on the longest computation of the algorithm must be at least: $$ \log ( n! ) \> \log (n/e)^n = n \log n - n \log e \> n \log n - 1.44 n = \Omega(n \log n). $$

Also, even in the case of comparison based-algorithms, an absolute lower bound of $n \log n$ (without the constant hidden in the $\Omega(\cdot)$ notation, as you write in the question) on the number of comparisons cannot possibly exist since, when $n=2^k$, each element in Mergesort is compared at most $k-1$ times, showing that the total number of comparisons is at most $n(k-1) = n \log n - n$.

Your proposed algorithm is not clear to me but, in general, if you change the model of computation by allowing other operations to be performed in addition to comparisons then the $\Omega(n \log n)$ lower bound does not apply anymore.

For example, given any constant $c$, in the word-RAM model you can sort a collection of $n$ elements between $0$ and $n^c$ in linear time using Radix sort, as long as the chosen word size $w$ allows to write $n$ in a (constant number of) memory word(s), as it is usually the case (it is standard to assume $w=\Theta(\log n)$).
> 2 votes

---
Tags: time-complexity, quantum-computing
---


# Question
Title: Is this a correct application of Rice-Shapiro theorem?
Let $\langle M\rangle$ be the encoding of a Turing machine as a string over $\Sigma=\\{0,1\\}$, and consider the language $L=\\{\langle M\rangle| \text{ $M$ is a Turing machine that accepts a string of length 2014} \\}$

I want to use The Rice-McNaughton-Myhill-Shapiro Theorem (page 14 in this) to prove that $L$ is acceptable:

Say $\mathcal{L}$ is the set of all acceptable languages that contain strings of length 2014.

* This set is monotone: every superset of a $L \in \mathcal{L}$ also contains strings of length 2014 so belongs to $\mathcal{L}$
* This set is compact: for every language in $\mathcal{L}$ I can choose the finite subset with strings of length 2014.
* This set is finitely acceptable: this is the part I'm confused about. Given every finite language of $\mathcal{L}$ is there a TM that can accept this set of finite languages?

# Answer
The application of the theorem is not correct. Note that $\mathcal{L}$ is a set of acceptable languages, and consider your first point. If you take an acceptable language $L$ that contains a string of length 2014, then it is not necessarily that every superset of $L$ is acceptable.

Regarding the last point, the answer is yes. Given an encoding $\langle L\rangle$ of a finite language $L \in \mathcal{L}$, it is easy to check whether $L$ contains a string of length $2014$. Indeed, we're assuming that the encoding encodes all the words of $L$ in some order, so you can simply traverse the encoding to look for a word of length 2014. Specifically, quoting from the link you attached:

> If $L$ is a finite language over $\Sigma$, then you can assume that $\langle L\rangle$ is the unique string over the alphabet $\Sigma \cup \\{ \\{,•,\\}, \epsilon\\}$ that contains the strings in $L$ in lexicographic order, separated by dots • and surrounded by braces {}, with $\epsilon$ representing the empty string. For example, if $\Sigma = \\{ 0, 1\\}$, and $L = \\{\epsilon, 0,01,0110,01101001\\}$, then $\langle L\rangle = \\{ \epsilon•0•01•0110•01101001\\}$.

So given such an encoding as input, you can go over it and check whether there is an infix of legnth 2014 between two consecutive dots •.

Finally, you can simply show that $L$ is acceptable directly by defining a TM that accepts it. Indeed, you can simply simulate the run of $M$ on all strings of length 2014 in parallel, and accepts iff $M$ accepts at least one of them.
> 2 votes

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


# Question
Title: For two sets of points find if second one is result of linear transformation of the first
Say we have two sets of points in vector-2 space (In actuality need to solve this problem in vector-3 space but decided to start with a simpler problem). The points in the second set are the result of transformation of the points in the first set. It's not known which point in the first set corresponds to which point in the second set. What needs to be calculated is if the points of the second set can be seen as the linear transformation of the first set. So basically finding whether there exists a 2 by 2 matrix, which if applied to the first set gives the second set. And if so calculating it.

Should a problem like this be solved using computational geometry, like sweep line algorithm to compare all points between sets?

# Answer
In 2D, a linear transformation has the form $v \mapsto Mv$ where $M$ is a $2\times 2$ matrix, so the transformation has four parameters. Thus, the transformation is uniquely determined if you have two points $p\_1,p\_2$ from the first set and two points $q\_1,q\_2$ and if you know that $p\_1$ transforms to $q\_1$ and $p\_2$ to $q\_2$. You can find this linear transformation explicitly by solving a system of linear equations.

Consequently, the following algorithms works:

1. Pick two points $p\_1,p\_2$ arbitrarily from the first set.
2. For each possible way to pick two points $q\_1,q\_2$ from the second set:
    * Find the unique linear transformation $T$ that maps $p\_1$ to $q\_1$ and $p\_2$ to $q\_2$.
    * Check whether applying $T$ to the first set gives you exactly the second set. If so, output $T$ and halt.
3. If you reach this point, output that no such linear transformation exists and halt.

This algorithm is guaranteed to be correct: it will find the linear transformation, if any exists, because we have tried all possible pair of points that $p\_1,p\_2$ could match with.

The worst-case running time is $O(n^3)$, if $n$ is the number of points in each set. That's because you loop over ${n \choose 2} = O(n^2)$ pairs of points in step 2. Each iteration of the loop involves solving a system of four linear equations (takes $O(1)$ time) and checking whether it is a valid solution (could take $O(n)$ time in the worst case, since you might have to apply $T$ to each point in the first set).

However, heuristically, I expect the running time will typically be $O(n^2)$. That's because typically you can reject most candidate transformations $T$ immediately: if you apply $T$ to one point in the first set, and get a result that is not in the second set, you can reject $T$ without applying it to any other points in the first set. Thus, heuristically, I expect that typically each iteration of the loop will usually complete in $O(1)$ time. That said, there do exist arrangements of the points where this is not correct.

The generalization of this algorithm is RANSAC, which can handle the situation where most points of the first set can be matched to the second set but some cannot.
> 3 votes

---
Tags: computational-geometry, sets
---


# Question
Title: minimum number of edges that should be added to an undirected graph to make it a tree
Basically, it's this rosalind problem.

You're given a number of nodes and an adjacency list. My initial guess was that the answer was the number of connected components minus 1, since by joining every connected component you would have a connected graph, and since it's stated that there are no cycles, that would be a tree.

Why is this approach wrong? The real answer is just the number of nodes-1-number of edges, which I understand, but can't see how is this not equivalent to my answer.

Also, the sample dataset given bugs me. I see three connected components so I don't see why the answer is not 2. Bear in mind, i'm almost new to graph theory so i'm sorry if i'm missing something simple.

# Answer
> 0 votes
Your first guess is correct. Sometimes there is more than one way to write the same solution.

Clearly, if there are $k$ connected components you'll need exactly $k-1$ edges to connect them (without forming any cycle).

On the other hand, a tree with $n$ nodes must have exactly $n-1$ edges, so if the graph is acyclic and already has $m$ edges, then it is missing $n-1-m$ edges.

Regarding the example: the given graph has $n=10$ vertices, $m=6$ edges, and $k=4$ connected components (not 3), so the answer is $3=k-1=n-m-1$. The sets of vertices in each connected component are $\\{1,2,8\\}, \\{3\\}, \\{4, 6, 10\\}$, and $\\{5, 7, 9\\}$.

---
Tags: graphs, trees
---


# Question
Title: Algorithm to schedule employees into days
I'm trying to build a scheduling app for a friend, but am stuck on how to sort the employees.

I have three holidays each with their own employee\_need:

thanks\_giving: 2

christmas: 3

new\_years\_eve: 2

I have employees who have a predetermined number of days they will work. The sum of the employee’s predetermined work days will always add up to the sum of the three holiday’s employee\_need. They also have ranked the holidays by preference, which should guide the scheduling process. The data looks something like this:

Polly:

days\_to\_work: 1

preferences: \[christmas, new\_years\_eve, thanks\_giving\]

Stan:

days\_to\_work: 2

preferences: \[thanks\_giving, christmas, new\_years\_eve\]

etcetera.

Right now my process of sorting is to

1. Fill each holiday with a list of all employees.
2. Loop through the employees, starting with those who have the most days off.
3. Loop through the employee's preferences and pull them from the one they most desire to have off that also has room for them to be taken off
4. Continue looping until the days are properly scheduled. If there is room to remove them from that day, I do so, until they are working the number of days they are supposed to.

The algorithm works a decent amount of time, but I really need it to work all the time.

Is anyone familiar with this kind of problem, and can point me toward a better methodology?

# Answer
This looks a lot like the stable marriage problem, itself related to the problem of matching in biparftite graphs. There are very efficient algorithms to solve both problems.
> 1 votes

# Answer
A standard approach is to use integer linear programming. You have a zero-or-one integer variable $x\_{e,t}$, with the intended meaning that $x\_{e,t}=1$ if employee $e$ is scheduled on timeslot $t$. Then each of your constraints can be expressed as a bunch of linear inequalities.

Scheduling problems are widely studied in operations research, so you could also look at standard tools for operation research problems (e.g., OR-Tools, as Yuval Filmus mentions).
> 0 votes

---
Tags: algorithms
---


title: Proving decidability

text:
# Question
Title: Proving decidability
Regarding the following languages $L\_1$ and $L\_2$, I want to prove that $L\_1$ is decidable and $L\_2$ is undecidable. I want to construct a turing machine which can decide $L\_1$ and reduce the halting problem to $L\_2$.

$L\_1$:
On input $w$ the turing machine $M$ never moves it's reading/writing head left. Where $w \in \\{0,1\\}^\*$ and $\langle M \rangle \in \\{0,1\\}^\*$ is the input of $L\_1$.

$L\_2$:
On input $w$ the turing machine $M$ moves it's reading/writing head in every step (making no neutral move). Where $w \in \\{0,1\\}^\*$ and $\langle M \rangle \in \\{0,1\\}^\*$ is the input of $L\_2$.

For $L\_1$: I know that a turing machine which can't move left, has no possibility of memorizing it's progress. It only knows the state it's in, so it's similar to a DFA. The difference is, that it reads and/or writes $\\{0,1\\}^\*$ and the blank symbol $\square$. It's also different to a right-moving turing machine because it can do a neutral move. My idea was to construct a $TM$ having two tapes. So that the original tape would scan the input and 'copy' it to the second one. The problem I came across is that I have no possibility of recognizing any loop cycles, so that if $w$ was finished, the $TM$ would never stop writing blank symbols because the tape is infinitely long. Another idea was to construct a $TM$ in which no state has a self-loop. But in this situation I still wouldn't have prevented this infinite writing and I need a $TM$ which halts on every input to prove $L\_1$ is decidable.

For $L\_2$: I want to reduce the halting problem $H = \\{w\\#x \mid M\_{w}$ halts on $x\\}$ to $L\_2$ so I can prove that $L\_2$ is undecidable. I had the idea of this function $f(\<M\>,x) \mapsto$ $\<M'\>\\#w\\#x$ where I put the input of $H$ into the function and get the input for the $TM$ $M\_{{L}\_{2}}$ which simulates $L\_2$. In addition to that I know that the definition of $M\_{{L}\_{2}}$ states how it never makes a neutral move but always moves and reads either left or right.

# Answer
For $L\_1$, consider a computation $T(w)$ of a Turing machine $T$ that never moves its head to the left with input $w$. Let $\Gamma$ be the tape alphabet (including the blank symbol) and $Q$ be the set of states of $T$. Notice that, at any given step during the computation, the future behavior of $T(w)$ is completely determined by:

1. The current state.
2. The tape symbol in the current cell.
3. The contents of the (infinitely many) tape cells on the right of the head.

There are $|Q|$ choices for 1, $|\Gamma|$ choices for $2$, and $\max\\{|w|,1\\}$ choices for 3 (since the contents of the tape to the right of the head are always a suffix of $w$ distinct from $w$, followed by infinitely many blank symbols).

To decide $L\_1$ it suffices to simulate $T(w)$ for $\eta = |Q| \cdot |\Gamma| \cdot \max\\{|w|,1\\} + 1$ steps. If $T(w)$ moves its head to the left during the simulation, then reject. Otherwise accept. To see that accepting is the correct choice notice that if $T(w)$ does not terminate within $\eta$ steps, then a state must be repeated at least twice, implying that $T(w)$ is in some loop. This loop can only involve states that appeared at least once during the first $\eta$ steps, showing that $T$'s head will never move to the left.

For $L\_2$ see this question.
> 0 votes

# Answer
A simple solution for $L\_1$: Check that for no input symbol there is a move to the left. As the machine will only ever encounter input symbols in it's long march to the right, this is enough.
> 0 votes

---
Tags: turing-machines, reductions, undecidability, halting-problem
---


title: Is my compilers assignment irrational?

text:
# Question
Title: Is my compilers assignment irrational?
In our assignment we are given a grammar (called minipython) and we are asked to implement some phases of compilation (parsing, some semantic analysis).

One of the requirements is to be able to check for types in an arithmetic expression (arithmetic expressions are only defined for integers). For example in the below code:

```
def add(x,y):
   return "hello world"
print add(2,1)+ 2

```

We are expected to detect such errors. However the language,like python, seems dynamic to me. Meaning that the return type of a function depends on the runtime (for example the function def f(x): return x

When we showed the instructor the code below:

```
a=0
b=1
if b>2:
    a = 'a'
c = a + b

```

The instructor told us we are supposed to detect such errors (in the arithmetic expression one type is string, the other is a number). And also he said we should run the code tracking the value of each variable.

Well... i haven't heard of a compiler that runs the program in order to detect errors. I mean that would be impossible if the language is Turing-complete right? (I'm not sure if minipython is though)

One of my classmates is attempting to do this by setting a limit on the times he remains on any loop or setting a max recursion depth. But I don't think this is right , i mean what compiler does this? I don't know what magic people do in static analysis tools but i don't expect that anyone runs the code in order to check type errors... unit tests are for that.

**My question**: Are my assignment's tasks irrational?? Can this language have a totally inferred type system? I'm really confused and I don't have much experience with compilers. Please correct me at any point if I have said anything that is wrong

I can also provide minipython's BNF if its necessary.

# Answer
Sorry, in complete generality this is an undecidable problem. Pick your favorite undecidable problem $P$ and an instance $a$, and write e.g.:

```
def value(a):
     if P(a):
         1
      else:
         "Hello, world!"

print(41 + value(a))

```

Under the (conservative!) assumption that all execution paths are possible, you see that the above is badly formed (`value` returns an integer or a string). That restriction is doable, and not too hard either: Do a postorder traversal of your AST, recording the possible types of each node. If any node could have conflicting types, flag a (possible) error.
> 1 votes

---
Tags: compilers, static-analysis
---


# Question
Title: Primality testing: Why is dividing a number $n$ by every integer between 2 and $\sqrt{n}$ an inefficient test?
In the paper "PRIMES is in P" the following is said (page 1):

> Let PRIMES denote the set of all prime numbers. The definition of prime numbers already gives a way of determining if a number $n$ is in PRIMES: try dividing $n$ by every number $m \leq \sqrt{n}$ — if any m divides $n$ then it is composite, otherwise it is prime. This test was known since the time of the ancient Greeks — it is a specialization of the Sieve of Eratosthenes (ca. 240 BC) that generates all primes less then $n$. The test, however, is inefficient: it takes $\Omega (\sqrt{n})$ steps to determine if $n$ is prime. An efficient test should need only a polynomial (in the size of the input = $\lceil \log n \rceil$) number of steps.

Firstly, isn't complexity $\sqrt{n}$ already polynomial?

Secondly, why would complexity $\lceil \log n \rceil$ represent an efficient algorithm? This seems somewhat arbitrary to me.

# Answer
> 12 votes
The complexity is measured as a function of the size of the input.
You don't have here an array of $n$ numbers but a number $n$.
The size of the input is $O(\log n)$ (to store a number $n$ you need $\lfloor log\_2(n) + 1 )\rfloor$ bits).
Hence, $O(\sqrt n)$ is not polynomial in the size of the input.

The answer to the second question is a direct consequence. Since the size of the input is logarithmic in $n$, an algorithm with logarithmic time complexity with respect to $n$ (and therefore, polynomial wrt the size of the input) would be efficient.

As an example, consider a number $M$ of size $n$, an algorithm with time complexity $O(log^k M)$ for a constant $k$, corresponds to a polynomial time algorithm (in the size of the input) of time complexity $O(n^k)$.

# Answer
> 7 votes
newbie's answer already explains it all. But if I had to add something to this, I'd put it in simpler words.

When you talk about a polynomial time algorithm, what you actually mean is that the running time of the algorithm is a polynomial *in the input length*. The input length is, roughly speaking, the number of keystrokes required to express the input.

To see why $O(\sqrt{n})$ is not polynomial in the input length, consider what happens when you add a new digit to the right end of your input. This requires just one extra keystroke. So, the input length goes up by just one. However, note that the *value* of the input goes up by a factor of $10$. So, now you need to do $\sqrt{10}\approx 3$ times as many divisions to check if your input is prime or not. Increasing the input length by just one results in a $3$-fold increase in work. This is clearly exponential.

The $O(\sqrt{n})$ time algorithm is an example of a pseudo-polynomial time algorithm. These are algorithms whose running times are a polynomial in the *numeric value* of the input, but not necessarily in the length of the input. Another common example of a pseudo-polynomial time algorithm is the dynamic programming algorithm for $0-1$ knapsack.

# Answer
> 0 votes
First of, you don't need to test the even numbers.

Second of, you don't need to test the numbers which end with a zero or with a 5.

Third of, you don't need to test any numbers which are not in the primorial base 30 a multiple of $30-+ (1,7,11,13)$

Fourth of you don't need to test any numbers which are not in the primorial base 210 a multiple of $210-+ (1,11,13,17,19,23...)$

Fifth of... Repeat.

# Answer
> -3 votes
So what is the issue here? The algorithm clearly requires (sqrt(n)//2) divisions by the respect to the N. So if I measure complexity by the function: input number -\> #of divisions, then I will get theta(sqrt(n)) complexity.

I believe the actual problem why this algorithm is inefficient that division is not a basic operation, and that the division's complexity is based on the length of divided numbers. Which I didn't see mentioned in any of the responses.

Also there seems to be a misunderstanding in expression of the complexity in "O" notation - O(sqrt(n)) is a subset of O(n) and therefore the algorithms should be more efficient, because power of 0.5 will be less than power of 1 for all positive integers. The other thing is that all algorithms with this (sqrt) complexity can be implemented only in such a way you showed - why is that inefficient. But I state that O(sqrt(x)) \<= O (x).

---
Tags: complexity-theory, primes
---