# Question
Title: Convert $1.75\times10^{15}$ to IEEE-32 format?
$1.75\times10^{15}$

I know how to convert decimal to binary

$(1.75)\_{10}$ is equal to $(1.11)\_2$

But to represent $10^{15}$ is the main problem for me. I can solve the question but this is the point where I got stuck. How can I represent $10^{15}$ in base 2 ?

# Answer
> 1 votes
You need to understand how the IEEE-754 standard for floating point numbers works. It is not simply converting the number to binary.

Instead, the 32 bits that compose the representation of the floating-point number are split into 3 fields: sign, exponent, mantissa. Their sizes are 1bit, 8bit, and 23bit, respectively. Each *field* is written in binary basis (unsigned).

If the value of the exponent field is $e$, and the value of the mantissa field is $m$ then, the these 32bits represent the number $$ 2^{e-127} \times (1 + m\cdot 2^{-23})$$ the $s$ bit determines if the number is positive or negative.

So, to represent the number $1.5\cdot 10^{15}$ you will need to set: $s=0$ (positive), $e=177$, and $m=2787263$. Calculate $2^{e-127} \times (1 + m\cdot 2^{-23}) = 2^{50} + 2787263\cdot 2^{27} = 1500000014041088$, which is the closest you can get to $1.5\cdot 10^{15}$ with 32bit representation.

Use https://www.h-schmidt.net/FloatConverter/IEEE754.html as a simple converter and a way to learn how this representation works.

(Oops, I demonstrated the above for 1.5e15, while the question was about 1.75e15. Nevermind, replace with $m=4649908$ to get 1.74999999e15).

# Answer
> 0 votes
In this example: $1.75 \cdot 10^{15} = 175 \cdot 10^{13}$.

Quick and dirty: You convert 175 into a floating point number, lookup $10^{13}$ in a table, and multiply the two numbers.

---
Tags: floating-point
---


# Question
Title: Given an non-deterministic finite automaton, will its determinization always have unreachable states?
Given an **NFA** that accepts the regular language ***L***, will its equivalent **DFA** which accepts the same language ***L*** always have unreachable states. If it does, why?

# Answer
No, there aren't always unreachable states. Consider the NFA with one state, $q$, and no transitions. (It accepts the language $\\{\epsilon\\}$ if $q$ is accepting, and accepts $\emptyset$, otherwise.)

If you determinize this automaton, you end up with a two-state DFA with a transition from the start state $\\{q\\}$ to the other state, $\emptyset$, so both states are reachable.
> 2 votes

# Answer
The powerset construction shows that for every NFA with $n$ states there is an equivalent DFA with $2^n$ states. Every example in which this is tight – that is, the minimal DFA has $2^n$ states – is a counterexample to your claim. You can find such an example, for arbitrary $n$ and over a binary alphabet, in this answer.
> 0 votes

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


# Question
Title: Simple algorithm to select separated points in closed intervals
Within the internal logic of a feature I'm working on, I've run into a need for a solution to essentially this problem:

$S$ is a finite union of $K \geq 1$ closed intervals,

$$S = \[a\_1,b\_1\] \cup \cdots \cup \[a\_K,b\_K\].$$

Select $N \geq 2$ points $x\_i \in S$, maximizing the smallest difference between any pair of points:

$$\Delta = \min\_{i \neq j} |x\_i-x\_j|.$$

In my case, the intervals are already disjoint and sorted ($a\_1 \leq b\_1 \< a\_2 \leq b\_2 \< \ldots \< a\_K \leq b\_K$), and solutions are only needed for "small" cases: $K$ and $N$ will both typically be 10 or smaller, and $K+N$ can never be more than 30. Since the numbers are small, it's more important to have a simple and maintainable solution than one with the best possible asymptotic computational complexity, though it's probably good to avoid an exponential- or factorial-time solution if reasonable.

**What is a straightforward and effective algorithm for this problem, given these limits on the interval and point counts?**

I did notice this existing question about the same problem, but it's asking about asymptotic complexity and about the effects of having overlapping intervals vs. intervals already normalized to disjoint ones. (Also, it currently has no answers.) Since it mentions linear programming, distance constraints, and Bellman-Ford, I looked into those on Wikipedia. But not being very familiar with those topics, I didn't really see how the problem translates into a graph path optimization problem. And I suspect implementing this sort of algorithm might be more complicated than I really need in my case.

I have worked out how to reduce the problem from selecting real/rational values to selecting natural number parameters: If $C\_i$ of the points are to be chosen from interval $\[a\_i,b\_i\]$, then

$$\sum\_{i=1}^K C\_i = N \\ \Delta = \min\_{1 \leq i \leq j \leq K} \frac{b\_j-a\_i}{-1+\sum\_{\ell=i}^j C\_\ell},$$

ignoring the terms with denominator $0$ or $-1$. And the point coordinates of a valid solution can be determined from knowing which of the ${K\choose 2}$ fractions in this $\Delta$ expression are exactly equal to $\Delta$.

So the dumbest brute force approach would be to find $\Delta$ for each of the ${{K+N-1}\choose{N}}$ possible partitions of $N$ into $K$ ordered buckets. One obvious improvement: $a\_1$ and $b\_K$ can always be two of the selected points. But that's probably way too many possibilities even with $N$ and $K$ just around 10.

It seems like some sort of "divide and conquer" strategy might be helpful, with splitting the sequence of intervals into two parts, deciding how many points in total to assign to each part, and solving those two subproblems, probably iteratively. But I haven't entirely determined the conditions that would make those subproblems produce valid answers to the larger problem.

# Answer
> 1 votes
First note that in any optimal solution we can always have $x\_1 = a\_1$ as we wish to maximize distances, and $x\_1 = a\_1$ unconditionally does that without sacrificing distance anywhere.

Secondly note that while our 'smallest differences' metric we want to optimize appears a global problem, it really is not if we also sort our $x$. We can have the equivalent definition:

$$\Delta = \min\_{1 \leq i \< K} \left( x\_{i+1} - x\_i \right)$$

Now suppose our candidate solution has value $\Delta$. Then given $x\_i$ we can find the leftmost $x\_{i+1}$:

$$x\_{i+1} = \min\_y \\{ y \mid y \in S \wedge y \geq x\_i + \Delta\\} $$

So we find $x\_1, x\_2, \dots$ until we are done. Repeatedly finding which interval in $S$ (if any) will contain $x\_{i+1}$ can be done in a combined $O(K)$ time during this process if you just keep track of the highest used interval so far. If there is no valid interval for $x\_{i+1}$, it means $\Delta$ is not a valid outcome, but if we find al values up until $x\_K$ it is.

So now we have a $O(K + N)$ time test to see whether a certain $\Delta$ is valid. But we can say with certainty that $\Delta \in \[0, b\_K - a\_1\]$. So we can do a binary search on this interval using our test to find a range which contains our optimal $\Delta$.

Since each step in this binary search halves the size of the interval that contains the optimal result, we can find optimal $\Delta$ (and corresponding $x\_i$) up to a precision of $2^{-p}(b\_K - a\_1)$ in $O(p(K+ N))$ time.

If you're a bit smarter you can terminate early and exactly as an optimal solution will always contain a limiting sequence of steps of the minimum distance $\Delta$ starting at the left part of an interval and ending at the right part of an interval. Thus we have $a\_i + k\cdot \Delta = b\_j$. In other words, if our remaining interval contains only a single value of the form $\frac{b\_j - a\_i}{k}$ for some $i \leq j$ and $k$, then that is the optimal value and you can terminate the search.

---
Tags: algorithms, optimization
---


# Question
Title: How to use Master Theorem with strange format of $b$ parameter?
I have a funcion $T: \mathbb{N}\to\mathbb{N}$ defined as:

$$T(n)=\begin{cases} 6 &\text{ if } n=0,\\ T(n-1) + 6n + 6 &\text{otherwise.} \end{cases}$$

How can I apply the Master Theorem to this problem? I have only seen the M.T. in one of these two formats:

$$T(n) = aT(n/b) + f (n)$$ $$T(n) = aT(n/b) + \Theta(n^c)$$

So I'm wondering how to transform the $T(n-1)$ to something usable. Is it even possible to apply the theorem to this kind of problem?

# Answer
> 4 votes
Not every recurrence falls within the bounds on the master theorem. Your recurrence is an example. However, by unrolling your recurrence, we can come up with an explicit formula: $$ T(n) = 6(n+1) + T(n-1) = 6(n+1) + 6n + T(n-2) = \cdots = \\ 6(n+1) + 6n + \cdots + 6\cdot 2 + T(0) = \\ 6(n+1) + 6n + \cdots + 6\cdot 2 + 6\cdot 1 = \\ 6 \sum\_{m=1}^{n+1} m = 6\frac{(n+2)(n+1)}{2} = 3(n+2)(n+1). $$

# Answer
> 0 votes
The master theorem simply doesn't apply in this case. There is no constant $b$ such that $n-1=n/b$ for all $n$. You must use some other technique to solve the recurrence.

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


# Question
Title: Designing a rationing algorithm for a store
Suppose I have a store and I have n units of item x. I want to sell all n units at the end of the day. I do not know how many customers will be coming in today. One customer could theoretically come in and buy all remaining units. This would not be desirable, as the next customer would not be able to buy this item, and would end up frustrated that we do not keep enough in stock.

In general, how does one design a rationing algorithm that balances the need to sell as much quantity as possible with serving the most amount of (unknown number of) customers? Is this even possible?

# Answer
> 1 votes
This sounds like a maximization problem. The algoritm should try to maximize something, let us call it utility. What You need to start with is to define the utility funktion: is it better to sell all to first customer or end the day with unsold goods?

---
Tags: scheduling
---


# Question
Title: $L = \{ a^{j!} \mid j \geq1\}$ is not context free by pumping lemma
How I use the pumping lemma to prove that the language $L = \\{ a^{j!} \mid j \geq1\\}$ is not context-free?

# Answer
Suppose $L$ is context free. Then, by pumping lemma, there exist two integers $h \ge 1$ and $1 \le x \le \min\\{h!, c\_L\\}$, where $c\_L$ is a constant depending on $L$, that satisfy the following:

* $a^{h!} \in L$
* $a^{h!-x} a^{xn} \in L$ for every $n \ge 0$.1

Now you only need to show that, for some value of $n$, $a^{h!-x} a^{xn} \not\in L$. Equivalently, you want to find a value of $n$ (possibly depending on $h$) such that $h! + (n-1)x$ cannot be written as $j!$ for any integer $j \ge 1$.

For example, if $h = 1$ then $x=1$ so you can pick $n=0$ to obtain $h! + (n-1)x = 0$.

When $h \ge 2$, you can pick $n=2$ so that $h! + (n-1)x = h! + x$, which is not a factorial of an integer as the following inequalities show: $$ h! \< h! + x \le 2 \cdot h! \< (h+1)! $$

---

1. This is a consequence of the general form of the pumping lemma and of the fact that all the words in your language contain only the character *a*.
> 1 votes

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


# Question
Title: How to properly compare performance of a prototype against a baseline
Assume that we have a baseline software B and a new prototype P that I want to compare with B. Ideally, I want to show that P performs some orders of magnitude or X times faster than B (on average).

I have m queries/problems that I run on each software with a timeout T. I record the raw running times $b\_1,\dots,b\_m$ of B and $t\_1,\dots,t\_m$ of P. It could be that for some (few) problems B is still faster than P, moreover it could be that there are very short times such as 0.01s or considerably longer ones, for instance, 3000s. Now my question is, what is a good measure to compare the performance of B and P quantitatively on average?

A straightforward (but probably crude) measure could be just computing the average running times $b\_a = \frac{1}{m}\sum\_{i=1}^m b\_i$ and $t\_a = \frac{1}{m}\sum\_{i=1}^m t\_i$, and taking $\frac{b\_a}{t\_a}$.

A variation of this measure is taking the average of times when both systems didn't timeout and counting the number of timeouts, although not sure how to get just one measure from these four values.

These two measures do not address one my concern related to the variance in the values of the times. For instance, for $m=2$, $b\_1=2500$s, $t\_1=8$s, $b\_2=2000$s and $t\_2=1000$s, the first measure is 4.4643. Does it mean that P performs on average 4 times faster? Would it be more reasonable to take the average of the normalised times $\frac{1}{m}\sum\_{i=1}^m \frac{b\_i}{t\_i}$? In this case it would be equal 157.25 and, seems to me, would better reflect the performance gains.

And again, a question is how to take timeouts into account properly.

I am sure that there should be standard approaches to comparing performance of two systems(for instance, databases), but I wasn't able to find anything quickly. I would also be grateful to see an explanation why one measure is better than the other, and what are the standard measures (at least on the scientific community).

# Answer
The general answer is of course: "It depends on the problem and the final utilization of your software".

The first question you should answer is what makes a given version query time so variable ? Is it query dependent ? Does the software have some buffering between queries ? Maybe a ressource variable availability ?

Generally the performance of an algorithm is evaluated considering the worst query possible. Let's take an example, you need an algorithm to find where a function change of sign:

You may loop on all points one by one or do a binary search. The former would sometimes performs faster if the searched point is one of the first. Nevertheless, in worst case it has to analyse all points whereas the latter finds the solution in logarithmic time.

Now if you have a timeout, the main metric you have is how many timeouts gets each solution. Maybe you even can identify what queries lead to timeout for each algorithm. In my opinion, there is no sense to compare average query time if some algorithm gets timeout more often.
> 1 votes

# Answer
1. Compare only cases when both systems don't timeout
2. Add separate metrics of timeout %
> 0 votes

---
Tags: performance
---


# Question
Title: Count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum
> count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum.

This is my recursive algorithm, what is wrong here?:

```
int f(int sum,int i){//sum is the current sum, i is the current indx (<=n)
    if(i>n){
        return ((2*sum)==(n*(n+1)/2));//ie sum==totalsum/2
    }
    int cnt=f(sum,i+1)+f(sum+i,i+1);//move to i+1 or add i to sum and then move to i+1
    return cnt;
}

```

```
For example, if n=7, there are four solutions:
{1,3,4,6} and {2,5,7}
{1,2,5,6} and {3,4,7}
{1,2,4,7} and {3,5,6}
{1,6,7} and {2,3,4,5}
ie f(0,1)=7

```

Answer is **f(0,1)** for any n (n is globally defined)

Thanks!

# Answer
> 3 votes
You are counting the number of *ordered* pairs of sets $(A,B)$ such that the elements of $A$ (and of $B$) sum to $n(n+1)/4$. Simply divide the result by $2$ to account for symmetries.

Besides, your algorithm has complexity $\Omega(2^n)$ so I doubt you'll meet the time constraint in the link you provided.

You can get an $O(n^3)$-time dynamic-programming algorithm as follows:

> Let $OPT\[n, x\]$ be the number of ways the numbers in $\\{1, \dots, n\\}$ can be partitioned into an ordered pair of sets $(A,B)$ such that the elements of $A$ sum to $x$ and those of $B$ sum to $n(n+1)/2 - x$.
> Then, $OPT\[0, 0\] = 1$, $OPT\[n\]\[x\] = 0$ if $n\<0$ or $x\<0$, and $$OPT\[n,x\] = OPT\[n-1, x-n\] + OPT\[n-1, x\]$$ Now, assuming that $n(n+1)/2$ is even, the solution you are looking for is: $\frac{1}{2}OPT\[n\]\[ n(n+1)/4 \]$.

---
Tags: algorithms, dynamic-programming, recursion
---


# Question
Title: Selecting items from two arrays without duplicate indices to get maximum sum
Given two arrays both of length n, you have to choose exactly *k* values from the array 1 and *n-k* values from the other array, such that the sum of these values is maximum, with constraint that if you choose a value from some index of any of the array you cannot choose from same index of second array.

I have encountered this type of question in many places but never able to solve it, and I always have an Intuition that this is a dynamic programming problem but never able to prove it. I do not quite understand If there exist a dynamic solution or not?

# Answer
There are two ways to interpret the problem.

**$k$ is part of the input**

Let $a=(a\_1, a\_2, \cdots, a\_n)$ and $b=(b\_1, b\_2, \cdots, b\_n)$ be the two given array. Suppose we have chosen $k$ values from array $a$, $a\_i$ where $i$ ranges over some index set $I$ that has $k$ elements. Then we have to choose the $n-k$ values from array $b$, $b\_j$ where $j$ ranges over all indices that are not in $I$. The sum of all numbers are

$$\sum\_{i\in I}a\_i+\sum\_{i\not\in I}b\_i=(\sum\_{i\in I}a\_i-\sum\_{i\in I}b\_i) + (\sum\_{i\in I}b\_i+\sum\_{i\not\in I}b\_i)=\sum\_{i\in I}(a\_i-b\_i)+\sum\_ib\_i$$

Since $\sum\_ib\_i$ is a constant, the sum reaches the maximum if $\sum\_{i\in I}(a\_i-b\_i)$ reaches the maximum. So we can select the $k$ largest elements in the array $a-b=(a\_1-b\_1, a\_2-b\_2, \cdots, a\_n-b\_n)$. The indices of the those elements are the indices of the elements in $a$ that we should choose.

The $k$ largest element can be selected in $O(n)$ time using quickselect, this algorithm can be implemented in $O(n)$ time. It can also be implemented in $O(n\log n)$ easily by sorting the array $a-b.$

**$k$ is not part of the input**

Solve the previous problem for $k=0$. Let the maximum sum obtained by $m\_0$.
Solve the previous problem again but for $k=1$. Let the maximum sum obtained by $m\_1$.
And so on.

Find the maximum number among $m\_0, m\_1, \cdots, m\_n$. That is the maximum sum we want in this interpretation the problem. A bit of extra bookkeeping will let us know the numbers we should select to reach that maximum sum.

**Exercises**

**Exercise 1.** How about the case of smallest sum?

**Exercise 2.** How about exactly $k-1$ values from the first array and $n-k$ values from the other array?
> 1 votes

# Answer
Answering My own Question: though time complexity of the greedy solution is much better.

Dynamic Programming Approach:

We Have: $array1$ and $array2$ both of length $n$ and we are required to choose exactly $k$ values from $array1$ and $n-k$ values from $array2$

Now we iterate through each value pairs from both the array and fill the array-dp row by row as we iterate through each column.

Create 2-Array dp\[n\]\[k\], Where,

$ n$ \- $length$ $of$ $each$ $array$

$ k$ \- $no$ $of$ $values$ $to$ $be$ $taken$ $from$ $array1$

**Definition:** $dp\[i\]\[j\]$ \- is the maximum value one can obtain if we are done iterating through $i$ value pairs and exactly $j$ values are taken from $array1$

**Formula:** $dp\[i\]\[j\]$ $=$ $max(array2\[i\]+dp\[i-1\]\[j\],array1\[i\]+dp\[i-1\]\[j-1\])$

**Explanation of Formula:** for each $(i,j)$ in the table we choose the maximum between two values that are,

1. if we choose a value from $array2$ that means we now need to choose exactly $j$ values from previous $i-1$ value pairs.(remember we needed to choose exactly $k$ values from $array1$)
2. if we choose a value from $array1$ that means we now have to choose exactly $j-1$ values from previous $i-1$ value pairs.

To get the maximum value obtainable we look for value of **dp\[n\]\[k\]**

**Time complexity:** $O(n\*k)$
> 1 votes

# Answer
Given two arrays A and B, for each index i your sum includes either A\[i\] or B\[i\]. You can start adding all B\[i\], then picking k indexes i and replacing B\[i\] with A\[i\], increasing the sum by (A\[i\] - B\[i\]).

You make the sum largest by calculating all values A\[i\] - B\[i\] and storing them into an array C, selecting the k largest values in C, and adding them to the sum.

Finding the k-largest element of an array can be done in O(n), and adding the k largest elements can again be done in linear time (add all elements that are greater than the k-largest element and count them at the same time. If you found k' elements greater than the k-largest, then there are at least k-k' elements equal to the k-largest.

Pseudocode: Let S be the sum of B\[i\] for 1 ≤ b ≤ n. Let C\[i\] = A\[i\] - B\[i\] for 1 ≤ i ≤ n. Find the k largest element of C, and let its value be K. Add all elements C\[i\] to S where 1 ≤ i ≤ n and C\[i\] \> k. Let k' be the number of elements C\[i\] for 1 ≤ i ≤ n with C\[i\] \> k. Increase S by (k - k') * K.
> 0 votes

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


# Question
Title: Confusion in speed up calculation for pipeline architecture
This is an online question I am trying to solve.

*You are given a non-pipelined processor design which has a cycle time of 10ns and average CPI of 1.4.If a pipelined processor having 5 stages are 1ns, 1.5ns, 4ns, 3ns, and 0.5ns, what is the best speedup you can get compared to the original processor?*

**Approach I:** In a pipelined architecture, in a steady state, the CPI tends to be 1 provided there is no fixed percent of NOPs. Thus Speed up = CPI\_non\_pipelined / CPI\_pipelined = 1.4 /1 = 1.4

**Approach II:** For converting the execution into pipelined, we need to reduce the cycle to match up phase duration. Thus pipelined cycle should be max of {phase durations} = max of {1ns, 1.5ns, 4ns, 3ns, and 0.5ns} = 4ns. So speed up = cycle\_duration\_non\_pipelined / cycle\_duration\_pipelined = 10/4 = 2.5

Wondering why is this difference! Any help will be much appreciated.

# Answer
Approach I is calculating the cycles per instruction change independent of frequency increase (presumably the unpipelined design has some hazards that are not present in the pipelined design forcing the unpipelined design to use multiple cycles for some instructions).

Approach II is calculating the *frequency* increase (cycle time decrease) from pipelining (ignoring overheads).

The actual performance increase, assuming a miraculous reduction of cycles per instruction from 1.4 to 1 and such foolishly unbalanced pipeline stages (and no overheads), would be the product of these two factors.

If the cycle time of the unpipelined design equals the total processing time of an instruction for the pipelined design, one would expect the CPI to be the same under ideal circumstances (no pipeline hazards). Somehow in this example, the unpipelined design manages to take longer on average to process an instruction than the pipelined design, which indicates that it is merely accidental that the times are equal; the stages of the pipelined design do not correspond to portions of the cycle time of the unpipelined design.

Pipelining does not reduce the amount of work and if each pipeline stage corresponds to an equal duration of work in the unpipelined design (i.e., work is not done faster) then the CPI would be equal, which implies that the pipelined design is not fully pipelined.

(Another alternative is that two distinct ISAs are being compared such that the more pipeline-friendly ISA used by the pipelined design uses 1.4 times as many instructions to avoid instructions that would take longer than 10ns to fully process.)
> 1 votes

# Answer
Some guesswork is needed here.

CPU 1 takes 1.4 cycles per instruction on average, which means 60% of instructions take 1 cycle, and 40% take 2 cycles (or there may be some instructions taking 3 cycles or more, but we ignore this at the moment).

If an instruction takes two 10 nanosecond cycles, then it cannot be performed in a pipeline taking a total of ten nanoseconds, so CPU 2 probably split the 2 cycle instructions into two, meaning that CPU 2 needs to execute 40% more instructions than CPU 1. That's quite predictably the same 40% that CPU 1 on top of each instruction. So the 40% more instructions make no difference.

What does make it difference is the 4 cycle pipeline speed, instead of 10 for COU 1. CPU 2 is 10/4 = 2.5 times faster.
> 0 votes

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


title: Normal colorings of cubic graphs to SAT

text:
# Question
Title: Normal colorings of cubic graphs to SAT
This problem is related to ”Normal coloring of cubic graphs (part 1) - a previous post. We repeat the definitions, slightly modified so as to get to the point (we define normal edge 5 colorability, rather than the more general normal edge $k$ colorability).

> **Definition** A *normal edge 5 coloring* (or *normal 5 coloring*) of a cubic graph $G$ is a proper coloring of the edges with 5 colors, so that for any edge $e\in E(G)$, the four edges adjacent to $e$ are colored with two colors, or with four colors.

Thus, an edge $e$ and its four adjacent edges might utilize three colors, or five colors.

> If three colors are used, $e$ is called *poor*, and if five colors are used, $e$ is called *rich*.

...

> **Question** I would like to know how to transform an instance of this problem to a CNF formula. That is, given a graph $G$, produce a CNF formula, such that a satisfying assignment can be translated back to a normal 5 coloring of the graph.

Note that working with the line graph of the cubic graph, as one would in dealing with a typical edge coloring problem, is a bit tricky (and that is all I dare to say).

Please advise if this question would be better off if posted in the theoretical computer science pages. Thanks in advance.

# Answer
> 4 votes
Start with $5|E(G)|$ variables $x\_{e,i}$, one for each $e \in E(G)$ and $i \in \\{1,2,3,4,5\\}$. Intuitively $x\_{e,i}$ means that edge $e$ is colored with color $i$.

A CNF formula $\phi$ can be obtained by the logical and of the following sub-formulas.

Each edge must have exactly one color:

* At least one color, for each $e \in E(G)$: $(x\_{e,1} \vee x\_{e,2} \vee x\_{e,3} \vee x\_{e,4} \vee x\_{e,5})$
* At most one color, for each $e \in E$, and $i,j \in \\{1,2,3,4,5\\}$ with $i\<j$: $(\overline{x\_{e,i}} \vee \overline{x\_{e,j}})$

The coloring must be proper:

* For each pair $e,f \in E(G)$ of adjacent edges and for each $i \in \\{1,2,3,4,5\\}$: $(\overline{x\_{e,i}} \vee \overline{x\_{f,i}} )$

If $e=(u,v)$ is an edge of $G$, let $f^e\_1,f^e\_2$ be the two edges other than $e$ that are incident to $u$, and $f^e\_3,f^e\_4$ be the two edges other then $e$ that are incident to $v$.

* For each $e \in E(G)$ add a new variable $r\_e$. This will encode "if $e$ is not rich, then $r\_e$ is true": Notice that if $e$ is rich then $r\_e$ can always be set to false. For every $i \in \\{1,2,3,4,5\\}$, every $j \in \\{1,2\\}$, and every $k \in \\{3,4\\}$: $(r\_e \vee \overline{x\_{f^e\_j, i}} \vee \overline{x\_{f^e\_k, i}})$
* For each $e \in E(G)$ add a new variable $p\_e$. This will encode "if e is not poor, then p\_e is true". Notice that if $e$ is poor then $p\_e$ can always be set to false. For every ordered tuple $(j, k, h)$ of $3$ distinct elements from $\\{1,2,3,4,5\\}$: $( p\_e \vee \overline{x\_{f\_1,j}} \vee \overline{x\_{f\_2,k}} \vee \overline{x\_{f\_3,h}}) \wedge ( p\_e \vee \overline{x\_{f\_1,j}} \vee \overline{x\_{f\_2,k}} \vee \overline{x\_{f\_4,h}}) \wedge ( p\_e \vee \overline{x\_{f\_1,j}} \vee \overline{x\_{f\_3,k}} \vee \overline{x\_{f\_4,h}}) \wedge ( p\_e \vee \overline{x\_{f\_2,j}} \vee \overline{x\_{f\_3,k}} \vee \overline{x\_{f\_4,h}}) $

Finally, this will encode "e is rich or e is poor":

* For every $e \in E(G)$: $(\overline{r\_e} \vee \overline{p\_e})$

---

If you have a satisfying truth assignment for $\phi$ then you can color edge $e \in E(G)$ with color $i$ iff $x\_{e,i}$ is true.

If you have a coloring then let $c(e) \in \\{1,2,3,4,5\\}$ be the color of edge $e$. You an get a satisfying truth assignment for $\phi$ by setting:

* $x\_{e,c(e)}= \top$, and $x\_{e,j} = \bot$ for $j \in \\{1,2,3,4,5\\} \setminus \\{ c(e) \\}$,
* $r\_e = \bot$ iff edge $e$ is rich,
* $p\_e = \bot$ iff edge $e$ is poor.

---
Tags: graphs, reductions
---


# Question
Title: Enumerate all paths in a given series-parallel graph
Series parallel graph is well-known and widely used. It has a single source and a single destination. The graph can be formed by means of recursive serial or parallel composition.

I have a graph dataset that is of this type, and I have to enumerate all paths in the series-parallel graphs. Are there any existed algorithms? If so, what is the time complexity of it?

# Answer
> 3 votes
## Treat SPG as DAG

We can see easily that every path from the source to the sink in a series-parallel graph (SPG) always goes nearer and nearer to the sink. It can never go backwards. There is no sideways. For the example in the illustration provided in the question, it can never move "up". This phenomenon can be proved easily by structural induction.

So we can view a SPG as a directed acyclic graph (DAG) naturally, where every edge is assigned the direction such that its head is nearer to the sink than its tail. For the SPGs in the illustration of the question, the head of an edge is lower than its tail.

## Many Algorithms for DAG

There have been many algorithms that lists all paths from a source node to a destination node in a DAG such as this one and this one.

## Time-complexity and space-complexity

For simplicity, **assume the given SPG is a simple graph.** (The case of multi-graph is not much different.) We have $|E|\le2|V|-3$. This inequality will not be used here; it is shown just to illustrate an SPG is a relatively simpler graph.

What is the maximum number of paths from source to sink in an SPG of $n$ vertices?

A rough estimate is $2^{\Omega(n)}$. In fact, we can show that the maximum number of paths from source to sink in an SPG of $n$ vertices is $3^{4 - (n-2)\\%5}4^{\lfloor(n-17)/5\rfloor +(n+3)\\%5}$ for all $n\ge13$, which is $\Theta(4^{n/5})$. So the worst time-complexity for all algorithms is about $\Omega(n4^{n/5})$.

If the algorithm stores that all paths in full detail before outputting anything or if the space used by output is counted towards usages, then the space-complexity is $O(n4^{n/5}$). However, if the space used by output is not counted towards space-complexity, the space-complexity can be reduced to $O(n)$ if we use a depth-first search such as the following code in Python, assuming the adjacency list of the SPG is given in the input.

```
def list_paths(g, path):
    children = g[path[-1]]
    if len(children) == 0:
        print(path)
    else:
        for node in children:
            path.append(node)
            list_paths(g, path)
            path.pop()

"""
Output all maximal paths from source in O(n)-working-space-complexity.
The parameter g is assumed to be an adjacency list that represents a valid DAG.
"""

def list_all_paths(g, source):
    list_paths(g, [source])

g = {1: [2, 3],
     2: [4, 5, 6],
     4: [7],
     5: [7],
     6: [7],
     7: [8],
     3: [8],
     8: [9],
     9: [10, 11],
     10: [12],
     11: [13],
     12: [14],
     13: [14],
     14: [],
     }

list_all_paths(g, 1)

""" Expected Output
[1, 2, 4, 7, 8, 9, 10, 12, 14]
[1, 2, 4, 7, 8, 9, 11, 13, 14]
[1, 2, 5, 7, 8, 9, 10, 12, 14]
[1, 2, 5, 7, 8, 9, 11, 13, 14]
[1, 2, 6, 7, 8, 9, 10, 12, 14]
[1, 2, 6, 7, 8, 9, 11, 13, 14]
[1, 3, 8, 9, 10, 12, 14]
[1, 3, 8, 9, 11, 13, 14]
"""

```

---

By the way, the number of all paths can be computed directly in $O(n)$ time and $O(n)$ space by either recursive dynamic programming or iterative dynamic programming following a topological sort.

---

**Exercise 1.** Show the maximum number of paths from source to sink in an SPG of $n$ vertices is $3^{4 - (n-2)\\%5}4^{\lfloor(n-17)/5\rfloor +(n+3)\\%5}$ for all $n\ge13$, where $\\%$ is the remainder operator. (For $n=12$, the maximum number is $4\times5=20$)

**Exercise 2.** Verify the algorithm above in Python still works if the given DAG `g` is not a simple graph, i.e., that might be parallel edges. What is its time-complexity and working-space-complexity when $g$ is a SPG that is not necessarily a simple graph?

---
Tags: graphs, time-complexity, enumeration
---


# Question
Title: Why is 2^32 in a 32-bit system = 4GiB and not 4Gib?
I was watching this video 32-Bit vs 64-Bit - The Advantage and at 1:19 (timestamp) the narrator mentioned the 4GB memory allocation for the 32-bit system. I later found out it should've been 4GiB but am still confused about the bit vs byte part. After all, it's a **32-"bit"** and not **32-"byte"** system.

# Answer
> 5 votes
"32-bit" describes the size of many of the units of data that the processor can use. In this context, it refers to the size of memory addresses. A 32-bit address can address $2^{32}$ distinct objects; in a *byte addressable* system, that means it can address $2^{32}$ distinct *bytes*.

We don't give addresses to individual bits in memory, but rather groups of bits. In a byte addressable system those are bytes (ie, octets of 8 bits); you can also have a word-addressable system where you can only address groups of, say, 32 bits. In a system with 32-bit addresses addressing 32-bit words, you'd be able to use $32 * 2^{32}$ bits, or 17GB! But nowadays most consumer hardware in phones/computers are byte addressable.

Concretely, in byte-addressable memory, the first 8 bits are referred to as byte 0, the next 8 bits are referred to as byte 1, and the last 8 bits are referred to as byte 4294967295. There is no pointer to individual bit 26; you instead need to read/write the entire byte that contains it (byte with address 3 contains the 27th bit)

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


# Question
Title: Scheduling algorithm with defined starting intervals and processing times
I need to design an algorithm for opening and closing some valves at regular times. The input schedule will look something like this:

* Every 5 minutes, open each of valves 1, 2, and 3 for 5 seconds
* Every 8 minutes, open each of valves 4, 5, and 6 for 10 seconds

The main constraint on this schedule is that only one valve can be open at a time.

If I were given just the first line from above as my schedule, the result would be like:

* `t % 300 = 0`: open valve 1
* `t % 300 = 5`: close valve 1, open valve 2
* `t % 300 = 10`: close valve 2, open valve 3
* `t % 300 = 15`: close valve 3

Adding in the second line raises some more problems, like what is the overall time period (i.e. the divisor in the `%`)? I believe this should be the least common multiple of all the time periods: `2400 = 300 * 8 = 480 * 5`. The schedules then become 8 and 5 copies, respectively, of the base schedules lined up sequentially.

I would want to determine if it is possible to fulfill the schedule. A simple sanity check is that the sum of all the open times is less than the total amount of time in the LCM, but I do not believe this is sufficient.

Second, I need to determine what the actual combined schedule is. I believe this would be a series of starting offsets for each valve's schedule. In the simple case I illustrated above, the offsets for each of valve 1, 2, and 3 are 0, 5, and 10, respectively.

I have looked into cyclic static scheduling, earliest deadline first algorithms, etc., but have been unable to synthesize this knowledge into the algorithm that I need here. The difficulty I see is that I do not have an *ending* deadline but a *starting* deadline: once the first valve opens at `t=0`, it must also open at `t=300, 600, 300*n`.

Other analogies I have considered are:

* packing byte patterns into a buffer without overwriting non-null values (view each time slice as a byte and the value at the byte is the number of which valve is open)
* dispatching trains of different speeds at given intervals and avoiding collisions
* arranging transparent pieces of plastic with some colored areas in a stack (or cylinder since this is repeated) so that a max of one color is present at any given point

To recap: I need to determine a schedule meeting the above criteria. If determining the schedule is computationally intensive, it would also be nice to quickly determine if such a schedule is possible as well.

Am I on the right track here? What should I search for to move forward in this algorithm design? Has this problem been solved already?

# Answer
> 1 votes
For this particular problem, you have an evident solution. If you work only in seconds, you have **GCD(5min, 8min) = 60s**. Moreover the sum of the required times of opening is $3\times 5 + 3 \times 10 = 45 s$.

Thus, you can assign to each valve an offset in the 60s period without any risk of collision. Then, you can decide independently for each valve for each 60s period if you actually use the assigned slot or not. That is to say one every 5 periods for valves 1, 2, 3 and every 8 periods for valves 4, 5, 6.

---
Tags: algorithms, scheduling
---


# Question
Title: Are graphic cards using the Map-Reduce model when performing typical gaming rendering
I know that the Map-Reduce model is a common model of parallel computation, perhaps some sort of standard way(?). I also know that graphic cards are specifically built for parallel computation. However when reading about the graphic pipeline I am not sure if there is a point at which the Map Reduce model is used. If not, what kind of parallel computations (just the general model of them so I could read more about it) are done during the typical rendering process of modern graphics cards? If it is used, where would that be on the below pipeline?

# Answer
This model isn't appropriate for rendering games, so it's not used in game engines. However, it can be implemented on GPUs. F.e. if you are going to implement Spark / relational algebra on GPUs, it may be a part of implementation.
> 0 votes

---
Tags: parallel-computing, graphics, mapreduce
---


title: Construct NPDA for the language

text:
# Question
Title: Construct NPDA for the language
$L=\\{w \mid w \in \\{a,b\\}^\*$, $\text{the number of a's is at least the number of b's} \\}$

I'm stuck trying to build an NPDA that accepts $L$.

# Answer
You need to design a NPDA that behaves as follows:

* If it reads "a" and stack is empty push "a" onto stack
* If it reads "b" and stack is empty push "b" onto stack
* If it reads "a" and top entry on stack is "a" the push "a" onto stack
* If it reads "b" and top entry on stack is "a" the pop "a" from the stack
* If it reads "a" and top entry on stack is "b" the pop "b" from the stack
* If it reads "b" and top entry on stack is "b" the push "b" onto stack

The top entry on the stack is therefore "a" if the NPDA has read more "a"s than "b"s, and is "b" if it has read more "b"s than "a"s. If the stack is empty then the NPDA has read equal numbers of "a"s and "b"s.

The accepting states are therefore if the top entry of the stack is "a" or the stack is empty.
> 1 votes

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


# Question
Title: how to maximise the no of edges selected in the graph in form of cycles of unbounded length?
Recently i started looking the perfect cycle cover algorithm related to kidney exchange problem where it is considered as NP-Complete for cycles restricted to a length\>2. However if cycles are not restricted by removing the length constraint it is considered as solvable in polynomial time ,But if perfect cycle cover doesn't exist and just we need to maximise the no of edges selected in form of cycles(So as to maximise the no of kidney exchanges), also no restriction on cycle's length, then how do we do it?

I am thinking of finding all cycles in the graph and then one by one remove the cycle's edges from the graph and then find the cycles in the residual graph and so on till no more cycles exist and then sum up all the cycle's lengths continuing this for all cycles and find the solution with maximum edges selected. But since this is not a good solution i want to know how to solve this maximising problem

# Answer
> 0 votes
A solution is to solve the assignment problem. Let's call $G(W, E)$ your initial graph and build a weighted bipartite graph $G'(U,V,E')$:

* on the first side $U$, you have one vertex $u\_i$ for $w\_i \in W$. In the kidney exchange analogy they are the donors.
* on the other side $V$, you also have one vertex $v\_i$ for $w\_i \in W$. In the kidney exchange analogy they are the recipients.

Now, for every $e \in E$ linking $w\_1$ and $w\_2$, put two edges in $E'$:

* $u\_1$ to $v\_2$, weight $0$
* $u\_2$ to $v\_1$, weight $0$

They represent the potential trade.

Also, for every $w\_i \in W$, add an extra edge in $E'$:

* $u\_i$ to $v\_i$, weight $1$

These edges represent the possibility to have no cycle for $w\_i$ in the optimal solution.

Now solve the assignment problem using Hungarian algorithm ($O(n^3)$), trying to minimize the edges selected in the assignment. You get the optimal solution maximizing the number of vertex covered by cycles.

---
Tags: algorithms, graphs
---


# Question
Title: How can you iterate through a hash table in constant time?
I am studying data structures and the book "How to Think About Algorithms" by Jeff Edmonds (pages 46-47) claim that:

> "Hopefully, all the elements that are in your set happen to be placed into different entries in the table. In this case one can
>
> * determine whether or not an element is contained in the set,
> * ask for an arbitrary element form the set,
> * determine the number of elements in the set,
> * **iterate through all the elements**,
> * and add and delete elements
>
> in constant time i.e independently of the number of items in the set."

when speaking about hash tables. I don't understand how it is possible to iterate through all the elements in constant time. Shouldn't it be $O(N)$ since we *iterate* through all of them?

# Answer
> 2 votes
What you said is true. You can't iterate through all the elements in a hash table in constant time. It would take $O(N)$. But the author is not actually talking about all the elements in the hash table, but to iterate though each single element (in which there is only one element, making it constant). It comes down to the assumption here:

*"all the elements that are in your set happen to be placed into different entries in the table."*

In this case for each element, there is a single node. If this was not true you need to form a link-list for the hash table table, that is when there is collision. Then for each element it's no longer a constant time. But whatever item in the hash table happens to have the longest list.

Again, the explanation isn't clear here. As it looks like the author is saying iterating through all the elements in a hash table, and not iterating through for each element.

# Answer
> 2 votes
I don't agree that the author was talking about iterating over a set with constant time per element. I've never seen iteration described in time per element. It's certainly not common enough to be an unspoken assumption. I would guess that instead it's simply an editing miss.

# Answer
> 0 votes
The definitions aren't clearly given in the fragment of the book that Google showed me.

Clearly, if the table has $N$ entries and each entry contains at most one item, you can iterate through all the items in time $\Theta(N)$. Now, if $N$ is some fixed constant, $\Theta(N)$ time is constant time – and the set has constant size. On the other hand, if $N$ is some variable that depends on the length of the input, then all the bets are off.

---
Tags: data-structures, time-complexity, hash-tables
---


# Question
Title: Why is the run time of an $f(n)$ space decider bounded by $2^{O(f(n))}$?
In the proof of Savitch's theorem from the 3rd edition of Sipser's Intro to Theory of Computation, Sipser claims that the maximum time that an $ f(n) $ space nondeterministic Turing machine that halts on all inputs may use on any branch of its computation is $2^{O(f(n))}$. However, I don't see why such a machine couldn't run for an arbitrary (but finite) number of steps in one of its branches. For instance, consider the following linear space machine for deciding SAT: on input $\phi$ rewrite the contents of the first tape cell $2^{2^{n}}$ times, then evalaute $\phi$ on every possible truth assignment. This machine runs in linear space (since it doesn't need to visit anything beyond the second tape cell for the first part of its execution), but its run time exceeds $2^{O(n)}$.

Despite the similar titles, my question is not a duplicate of this one. The confusion in the linked question is about the constants that result from using an arbitrary alphabet. The author admits that they understand the $2^{O(f(n))}$ time bound for machines that use a binary alphabet (which is precisely what I don't get), and therefore none of the answers address my question.

# Answer
Because, if you only use $f(n)$ tape cells, there are at most $|\Sigma|^{f(n)}$ possible strings you can have written on the tape, at most $f(n)$ different places the tape head could be, and at most $|Q|$ different states the Turing machine could be in. That means there are at most $|Q|\\,f(n)\\,|\Sigma|^{f(n)}$ different configurations for the machine. If the machine runs for more steps than that, it must visit the same configuration twice.

For a moment, let's pretend the machine is deterministic. If it visits the same configuration twice, it will take exactly the same sequence of steps and visit a third time, and infinitely often, so it cannot terminate. However, we know that it *does* terminate for all inputs. Therefore, it runs for at most $|Q|\\,f(n)\\,|\Sigma|^{f(n)}=2^{O(f(n))}$ steps.

But, actually, the machine is nondeterministic. Still, if some computation path visits the same configuration twice, we know that there is a computation path in which, by making the same nondeterministic choices again, the machine reaches the configuration a third time, and so on. Since we're told that *every* computation path terminates, we know that no computation path visits the same configuration twice, so we're done as in the deterministic case.
> 5 votes

# Answer
Consider all the possible configurations of a Turing machine $T$: if $S$ is the number of its states, $\Sigma$ is its alphabet, including the empty character, and $f(n)$ is an upper bound on the space used, then you only have $$ |S| \cdot f(n) \cdot |\Sigma|^{f(n)} = |S| \cdot f(n) \cdot 2^{f(n) \cdot \log\_2 |\Sigma| } = 2^{O(f(n))} $$ configurations (where I used the fact that $|S|$ and $|\Sigma|$ are constants w.r.t. $n$, and the multiplicative factor $f(n)$ accounts for the possible positions of the tape head).

Consider any execution of $T$: if $T$ ends up in the same configuration $s$ twice then it ends in $s$ an infinite number of times, i.e., it does not terminate.

This means that, if the execution of $T$ terminates, then $T$ must have ended up in each configuration at most once, i.e., the number of steps is upper bounded by the number of configurations.
> 3 votes

---
Tags: complexity-theory, turing-machines, space-complexity, nondeterminism
---


title: Analysis of straight insertion

text:
# Question
Title: Analysis of straight insertion
I'm currently reading through N. Wirths': Algorithms + Data Structures = Programs. I'm not sure, but I think there might be an error in the analysis of the provided straight insertion sort. Screenshot of the relevant paragraph is here: screenshot

*Edit*: sentinel item `a[0] = x`, the current item that I want to insert at the appropriate place.

Sorry, another screenshot of relevant paragraph is here: screenshot2

```
    type index = 0..n
    var a: array[0..n] of item

    procedure straightinsertion
        var i,j: index; x: item;
    begin
        for i := 2 to n do
        begin x := a[i]; a[0] := x; j := i-1;
            while x.key < a[j].key do
                begin a[j+1] := a[j]; j := j-1;
                end;
            a[j+1] := x
        end
    end

```

I think, that the analysis of the number of comparisons might be wrong. He claims, that the number `C_i` of key comparisons in the `i`-th sift is at most `i-1`. But shouldn't it be `i`? Because at the worst case, since we are using sentinel, we have to make an extra comparison with the sentinel too. I claim, that:

* `C_min = n-1`
* `C_ave = 1/4 * (n^2 + 3n - 4)`
* `C_max = 1/2 * (n^2 + n) -1`

The number of moves `M_i` should then be `(i-1)+2`. `M_min, M_ave, M_max` are, I believe, correct in the text (screenshot).

Could you please confirm if I'm right or is there something I'm missing?Thank you all very much!

# Answer
> 0 votes
**Edit:** My apologies, misunderstood what you meant by sentinel earlier. It seems to me that you are correct, and this is indeed a typo. When you include comparison against the sentinel at $a\[0\]$, you perform $i - 1 + 1 = i$ comparisons on a worst case sift.

---
Tags: algorithms, algorithm-analysis, runtime-analysis, sorting
---


# Question
Title: Still not understanding why the Knapsack Problem does NOT have a polynomial-time solution
All the explanations for why the $O(nW)$ DP algorithm that solves the Knapsack Problem is NOT polynomial repeat the same thing: it is the *length* (in bits) of the input that matters, not its value/magnitude. The solution has the following structure:

```
# some preprocessing
for i in range(n):
    for w in range(W):
        # compute stuff

```

They repeat the same example: $W=10\_2=2$, but $W=100\_2=4$, i.e. every extra bit doubles the length of $W$. Here's my confusion

* Why can't I apply the same logic for $n$?

# Answer
> 4 votes
As you're aware, "polynomial time" means that there is a polynomial $p$ such that the running time on input $X$ is at most $p(|X|)$.

An input to the knapsack problem consists of a list of $n$ weights, a list of $n$ values and a maximum weight $W$. Since each weight and each value must take at least one bit to write down, we know that $n\<|X|$. But $W$ is written in binary and you can easily produce an instance where, say, $W$ has bit-length $|X|/2$. In such an instance, the running time of $nW$ is about $|X|2^{|X/2|}$, which isn't polynomial.

The key point that you've missed is that $n\<|X|$ because, effectively, the input specifies $n$ in unary. (That is, if the weights are $1,3,2,5,2,2$, then $n$ is basically the number of commas, modulo the usual off-by-one error.)

---
Tags: knapsack-problems
---


# Question
Title: Lambda Calculus as a branch of set theory
This answer to a question about whether C is the mother of all languages contained an interesting tidbit that I am curious about:

> The functional paradigm, for example, was developed *mathematically* (by Alonzo Church) as a branch of set theory long before any programming language ever existed.

Is this true? What is the link between these topics that is so fundamental as to make lambda Calculus an outgrowth of set theory? The best I can come up with is that standard mathematical functions possess domains and codomains.

# Answer
It's false. The $\lambda$-calculus arose through efforts to understand foundations of mathematics. Nowadays some people mistakenly equate foundations with set theory. The Stanford Encyclopaedia of Philosophy has a very good writeup on the $\lambda$-calculus, as well as its history, I recommend it.
> 10 votes

---
Tags: lambda-calculus, sets, history
---


title: Algorithm for deducing values

text:
# Question
Title: Algorithm for deducing values
I have a group of logical conditions and need to deduce values that would **NOT** satisfy them. For example:

1. `City != New York && Location = Museum`
2. `City = New York && Location = Store`
3. `City != New York && Location != Subway`
4. `Elevation = 100'`

So some values that would **NOT** satisfy any of those conditions are:

* `City: New York, Location: Museum, Elevation: 110'`
* `City: Moscow, Location: Subway, Elevation: 110'`

I just need to derive values, any values, that will fail to satisfy all conditions. (Application: Generating manual tests.)

It's easy to figure out values to violate any one condition, but I'm having trouble coming up with an algorithm to generate values that will violate them all. I have all the logical conditions in a data format (JSON, e.g. `{ key: 'City', operator: '=', referenceValue = 'New York' }`).

---

This solution worked for me, but I'm not making it an answer because it's not super-elegant and I'm not sure it would work in all cases.

1. Create a value hash for each key, populating it with all possible values for that key.
2. Each value for each key is marked ALLOWED initially, but can later be marked CONTINGENT or DISALLOWED. (I created a ValueDisposition class to manage this.)
3. Find relevant conditions for each key, and analyze their effect on values. For example analyzing condition 4 above for `elevation` would mark `100'` as DISALLOWED (because we are looking to find data that violate all the given conditions). Analyzing condition 2 above for `City` would mark `New York` as CONTINGENT because it is only a valid value if the contingent condition `Location = Store` is violated (I record contingent conditions in the ValueDisposition class as well).
4. Do a first pass finding an ALLOWED value for as many keys as possible.
5. Do a second pass on CONTINGENT values, violating the contingent conditions to derive acceptable value-sets (for example, with `New York` it's easy to violate `Location = Store`). I was able to do this easily for all of my condition-sets, but this could get challenging (requiring recursion?) if you had contingent conditions involving multiple keys.

# Answer
As the comments indicated, if the goal is to invent fictional cities, and you allow more three or more conjuncts in a condition, then any SAT problem is reducible to your problem.

Depending on the type of constraints, this is probably a more general problem, called "SAT Modulo Theories" or SMT for short. It's the boolean satisfiability problem, plus the theory of whatever your constraints are.

For example, if you allow inequalities:

```
Elevation < 200

```

You now need to decide what kinds of constraints those are. If elevation is an integer, and you allow constraints between properties (e.g. number of subway stations is less than the number of suburbs), then solving the problem is, in general, an integer programming feasibility problem.

But chances are that you don't need to worry about that for your scale. If we allow the closed-world assumption, in the sense that the set of city names and locations etc is fixed, then backtracking search is probably good enough. A small Prolog program will do the job.

Here, I used GNU Prolog, and attached the finite domain solver for elevation:

```
city(new_york).
city(moscow).
city(london).
city(paris).

location(museum).
location(store).
location(subway).
location(grand_bazaar).

% The lowest city in the world is Jericho, and the highest city
% is La Paz.
elevation(Elevation) :- fd_domain(Elevation, -846, 11975).

satisfying_cities(City, Location, Elevation) :-
    city(City),
    location(Location),
    elevation(Elevation),
    (City = new_york ; \+ Location = museum),
    (\+ City = new_york ; \+ Location = store),
    (City = new_york ; Location = subway),
    (Elevation #\= 100).

```

And running the query:

```
?- satisfying_cities(City, Location, Elevation).

```

gives some answers, the first of which is:

```
City = new_york
Elevation = _#0(0..99:101..127@)
Location = museum

```

The FD constraint on elevation is a little hard to read, but it's essentially saying that any elevation between 0 and 99 or 101 and 127 will do.
> 1 votes

---
Tags: logic
---


# Question
Title: Using pumping lemma to show a language is not context free(Complicated)
How can i show that the following long language is not context free using the pumping lemma?

$L=\left\\{abc^{i\_1}bc^{i\_2}...bc^{i\_{2m}}def^{j\_1}ef^{j\_2}..ef^{j\_{2n}}ghq^{k\_1}hq^{k\_2}...hq^{k\_o}\right\\}$

Such that:

$m,n,o \geq 1;$

$m\>n\>o\>0;$

$i\_1,i\_2,...,i\_{2m} \geq 0;$

$j\_1,j\_2,...,j\_{2n} \geq 0;$

$k\_1,k\_2,...,k\_o \geq 0$

And how can I conclude from that $L=\left\\{0^i1^j2^k|1\le \\:i\<j\<k\right\\}$ is not a context free language?

I have been struggling with it for many hours, would really appreciate an explanation I can follow and learn from. The examples given in class are simpler and not on that level, and I don't know which z to take and how to break it in order to deduct in a proof that L is not context free.

Could you please give a slow explanation so I could learn fast?

My attempt for the ***first part***:

Proving by negation that L is not a context free language: Assuming L is a context free language, then there should exist a pumping length P for which any string S such that $|S| \leq P$ can be divided into 5 pieces(uvxyz) while obeying the pumping lemma rules. Because of the information on the question, I'll focus on the first part of the lemma, i.e: $\forall i: uv^ixy^iz \in L$. The structure of a typical word from L will be:$S=abc^{p\_1}bc^{p\_2}...bc^{2p\_i+2}def^{p\_1}ef^{p\_2}...ef^{2p\_i}ghq^{p\_1}...ghq^{2p\_i-1}$. vxy cannot contain c,f,q's, We'll divide it into the following cases based on vxy. Don't know how to divide it or how to continue, would really appreciate your assistance with it. Very important to me

My attempt for the ***second part***(I don't understand it well enough to solve the first part, I will ask for your help with it):

Proving by negation that L is not a context free language: Assuming L is a context free language, then there should exist a pumping length P for which any string S such that $|S| \leq P$ can be divided into 5 pieces(uvxyz) while obeying the pumping lemma rules. Because of the information on the question, I'll focus on the first part of the lemma, i.e: $\forall i: uv^ixy^iz \in L$. The structure of a typical word from L will be:$S=0^p1^p2^p$. vxy cannot contain a,b,c's, We'll divide it into the following cases based on vxy:

1. Doesn't contain 0: pumping S with 0 to obtain $uv^0xy^0z=uxz$. in this case, there are fewer 1 or 2, so not in L.
2. There's 0 but not 2: pumping S with 2 to obtain $uv^2xy^2z$, meaning more 0's than 2's, so it is not in L.
3. There are no 2's: pumping S with 2 to obtain $uv^2xy^2z$, meaning more 1's or 0's than 2's, so it is not in L.

Since each option was checked and each one contradicted, It can be safe to assume that $L=\left\\{0^i1^j2^k|1\le \\:i\<j\<k\right\\}$ is not a context free language since it does not adhere to the pumping lemma.

Thank you very much

# Answer
Start with a long enough string $w$ in $L$ in which $m=p+2,n=p+1,o=p$ and

* $i\_1,...,i\_{2m}=0$
* $j\_1,...,j\_{2n}=0$
* $k\_1,...,k\_{o}=0$

$w = a\\; b^{2(p+2)}\\; d\\; e^{2(p+1)}\\; g\\; h^{p} $

Then apply pumping lemma (it should be easier ;-).

If you want to "reduce" $L$ to $L' = \left\\{0^i1^j2^k|1\le \\:i\<j\<k\right\\}$ then you must use closure properties, in particular CFLs are:

1. closed under homomorphism
2. closed under reverse homomorphism
3. closed under reversal

The homomorphism that you can use is: $H(a) = H(c) = H(d) = H(f) = H(g) = H(q) = \epsilon, H(b) = \bar{2}, H(e) = \bar{1}, H(h) = \bar{0}$

Applying $H$ to the language gives $H(L) = \\{ \bar{2}^{2m} \bar{1}^{2n} \bar{0}^{o} \mid m \> n \> o \> 0\\}$

Then you can use a reverse homomorphism $\varphi(2)=\bar{2}\bar{2}, \varphi(1)=\bar{1}\bar{1}, \varphi(0) = \bar{0}$ and you get:

$\varphi^{-1}( H(L)) = \\{ 2^m 1^n 0^o \mid m\>n\>o\>0 \\}$

and finally apply closure under reversal:

$(\varphi^{-1}( H(L)))^R = \\{ 0^o 1^n 2^m \mid 0\<o\<n\<m \\} = L'$

If $L$ is CF then by closure properties $(\varphi^{-1}( h(L)))^R = L'$ should be CF, which is not the case.
> 3 votes

# Answer
Let us check the first part, $L=\left\\{abc^{i\_1}bc^{i\_2}...bc^{i\_{2m}}def^{j\_1}ef^{j\_2}..ef^{j\_{2n}}ghq^{k\_1}hq^{k\_2}...hq^{k\_o}\right\\}$ where $m\>n\>o\>0$, $i\_1,i\_2,...,i\_{2m} \geq 0$, $j\_1,j\_2,...,j\_{2n} \geq 0$, $k\_1,k\_2,...,k\_o \geq 0$. Note the "where" clause means $\\#\_b(w)$ and $\\#\_e(w)$ are even and $\\#\_b(w)\>\\#\_e(w)\>2\\#\_h(w)$.

Assume $L$ is context-free for the sake of contradiction. Then there is a $p\ge1$, the pumping length such that every word in $L$ of length no less than $p$ can be written as $uvxyz$ such that $|vxy| \le p$, $|vy| \ge 1$ and $uv^kxy^kz$ is also a word in $L$ for all nonnegative number $k$.

Consider $w=a{\underbrace{bb\cdots b}\_{2(p+2)\text{ times}}}$$d\underbrace{ee\dots e}\_{2(p+1)\text{ times}}$$g\underbrace{hh\cdots h}\_{p\text{ times}}$, a word that is in $L$ but "almost not in $L$".

Decompose $w=uvxyz$ where $v$ and $y$ together is the pumpable part of the word. There are following cases of the pumpable part.

* The pumpable part contains $a$, $d$, or $g$.

One of the them will disappear if we pump down by letting $k=0$, i.e., $uv^0xy^0z=uxz$.
* Otherwise, the pumpable part must contain at least one of $b,e,h$.

+ the pumpable part does not contains $h$. So it must contain either $b$ or $e$.

    Pumping down by letting $k=0$ will decrease either $\\#\_b(w)$ or $\\#\_e(w)$ without changing $\\#\_h(w)$.
    + Otherwise, the pumpable part contains $h$. Since $vxy$ is too short to contain both $b$ and $h$, the pumpable part cannot contain $b$.

    Pumping up by letting $k=2$ will increase $\\#\_h(w)$ without changing $\\#\_b(w)$.

In all cases, $uvxyz$ can be pumped into a word not in $L$. So $L$ does not behave as described by the pumping lemma, which invalidate our assumption that $L$ is context free.

---

**Exercise**. Show that $\left\\{w\in \\{a,b,c\\}^\*\mid \\#\_a(w)\> \\#\_b(w)\text{ and }\\#\_a(w)\> \\#\_c(w) \right\\}$ is not a context-free language.
> 1 votes

---
Tags: computability, automata, context-free, pumping-lemma
---


# Question
Title: Getting from one language to the other using closure properties(automata)
I am trying to deduct how i can, using closure properties, deduct that since the following language is not context free $$L=\left\\{abc^{i\_1}bc^{i\_2}...bc^{i\_{2m}}def^{j\_1}ef^{j\_2}..ef^{j\_{2n}}ghq^{k\_1}hq^{k\_2}...hq^{k\_o}\right\\}$$

Such that:

$m,n,o \geq 1;$

$m\>n\>o\>0;$

$i\_1,i\_2,...,i\_{2m} \geq 0;$

$j\_1,j\_2,...,j\_{2n} \geq 0;$

$k\_1,k\_2,...,k\_o \geq 0$

this language is also: $$L=\left\\{0^i1^j2^k|1\le \\:i\<j\<k\right\\}$$

My attempt: basically, they both look very similar, but I am not sure the coming procedure is correct: If we take $L=\left\\{abc^{i\_1}bc^{i\_2}...bc^{i\_{2m}}def^{j\_1}ef^{j\_2}..ef^{j\_{2n}}ghq^{k\_1}hq^{k\_2}...hq^{k\_o}\right\\}$, Unionize bc, ef and hq to obtain the following: $L=\left\\{aB^{i\_{2m}^\*}dE^{j\_{2n}^\*}gH^{k\_o^\*}\right\\}$, And then using assignment or homomorphism, defining $h:B^{i\_{2m}^\*} -\> 0^{i\_{2m}^\*}$, $h:E^{i\_{2n}^\*} -\> 1^{j\_{2n}^\*}$ , $h:H^{k\_o^\*} -\> 2^{k^\*\_o}$ obtaining: $L=\left\\{a0^{i\_{2m}^\*}d1^{j\_{2n}^\*}g2^{k^\*\_o}\right\\}$. Since we can decompose string S using the pumping lemma into $S=uvxyz$ as we choose, We can only regard the $0^{i\_{2m}^\*}1^{j\_{2n}^\*}2^{k^\*\_o}$ part. Because of that, And knowing in advance that $L=\left\\{abc^{i\_1}bc^{i\_2}...bc^{i\_{2m}}def^{j\_1}ef^{j\_2}..ef^{j\_{2n}}ghq^{k\_1}hq^{k\_2}...hq^{k\_o}\right\\}$ is not context free, we can deduct that $L=\left\\{a0^{i^\*\_{2m}}d1^{j^\*\_{2n}}g2^{k^\*\_o}\right\\}$ is not context free as well.

Would really appreciate your corrections or knowing if there exists a better and easier way to deduct that.

Thank you very much.

# Answer
If I understand your argument correctly, you are reducing languages in the wrong direction.

> If $L$ is not context-free, then $K$ is not context-free.

Is equivalent to

> If $K$ is context-free, then $L$ is context-free.

We have to reverse the construction, as we are using the closure properties of the context-free languages. In do not know of any useful closure properties of the non-context-free languages.

PS. The pumping argument seems out of place here.
> 1 votes

---
Tags: computability, automata, context-free, pumping-lemma, closure-properties
---


# Question
Title: What is the time complexity of the below code?
```
i=12

while( i < n )

{

i=i^5

i=i/3

i=i∗7

}

```

What is the complexity of the given program?

# Answer
Let $V(0)=12$ and $V(j)$ be the value of the variable $i$ immediately after the $j$-th iteration for $j \ge 1$.

$$ \begin{align} V(j) &= \frac{7}{3} \cdot V(j-1)^5 \\ &= \left(\frac{7}{3}\right)^{1+5} \cdot V(j-2)^{25} \\ &= \left(\frac{7}{3}\right)^{1+5+25} \cdot V(j-3)^{125} \\ &= \dots \\ & = \left(\frac{7}{3}\right)^{\sum\_{k=1}^{j-1} 5^k} + V(0)^{5^j} \\ &= \left(\frac{7}{3}\right)^{\frac{5^j - 1}{4}} + 12^{5^j} \end{align} $$ (I'm hand-waving a bit when the dots are used. If you want a formal proof you can use induction on $j$).

For your algorithm to stop you need that $V(j) \ge n$. When does this happen?

> Notice that $V(j)$ is monotonically increasing. Then, you need more than $s = \lfloor \log\_{5} \log\_{12} n/2 \rfloor$ iterations since: $$V(s) = \left(\frac{7}{3}\right)^{\frac{5^s}{4}} + 12^{5^s} \< 2 \cdot 12^{5^s} \le n,$$ and at most $S = \lceil \log\_{5} \log\_{12} n \rceil$ iterations since: $$ V(S) = \left(\frac{7}{3}\right)^{\frac{5^S}{4}} + 12^{5^S} \> 12^{5^S} \ge n. $$ Each iteration requires constant time (assuming that each arithmetic operation can be carried out in $O(1)$ time, which might or might not be reasonable if you're dealing with large values). Therefore the time complexity is $\Theta(\log \log n)$.
> 2 votes

---
Tags: time-complexity
---


# Question
Title: why is discrete maths needed to understand algorithms?
I am new to algorithms. I need to know is it necessary to study discrete maths to understand algorithms. If so, why? In particular, is it necessary for understanding algorithms or is it only necessary for making your own algorithms (when you need to prove algorithm correctness).

# Answer
> 2 votes
There are several angles to this question.

First, most algorithms work on *discrete abstractions* like graphs, trees, matrices, sequences. To understand what the algorithm does, you need some acquaintance with those. They are staple of discrete mathematics. To prove the algorithm works as claimed relies on said properties, and the proof is essentially doing discrete mathematics.

Second, to use algorithms successfully, you need to know how to map your real work problem to the above abstractions, that again means knowing their particularities.

Third, you usually will want to derive performance numbers, either to verify the algorithm works within given constraints (time, space), or to compare alternative approaches and evaluate tradeoffs. Again, a job for discrete mathematics.

Sure, you certainly can do a lot without going deeply into discrete mathematics (at least not openly), but it is a valuable toolbox.

---
Tags: algorithms, discrete-mathematics
---


# Question
Title: Examples of exact computation of Kolmogorov complexity?
First question: It is known that Kolmogorov Complexity (KC) is not computable (systematically). I would like to know if there are any "real-world" examples-applications where the KC has been computed exactly and not approximately through practical compression algorithms.

Second question and I quote from the "Elements of Information Theory" textbook: "one can say “Print out the first 1,239,875,981,825,931 bits of the square root of e.” Allowing 8 bits per character (ASCII), we see that the above unambiguous 73 symbol program demonstrates that the Kolmogorov complexity of this huge number is no greater than (8)( 73) = 584 bits. The fact that **there is a simple algorithm** to calculate the square root of e provides the saving in descriptive complexity." Why take the 584 bits as an upper bound for the KC and not include the size of the actual "simple algorithm" that calculates the square root of e?? It is like cheating...

# Answer
The underlying problem with the example you quote is that it's informal and completely imprecise. As you say, why don't we include the size of the "simple algorithm"? Why are we allowed to assume that it is known what "$e$" is?

Formally, Kolmogorov complexity is defined with respect to a particular encoding of Turing machines. If you fix an encoding, then the Kolmogorov complexity of a string $x$ is $K(x)$, the length of the shortest encoding of a Turing machine that prints that string when started with empty input. (Informally, but still reasonably precisely, you can think of Turing machine encodings as programming languages, and the encoding of a specific Turing machine is a program in that language.)

A key point is that, if we choose different encodings, we get different values for the Kolmogorov complexity. At the level of the informal example, we could both agree that "DO IT!!" means "Print out the first 1,239,875,981,825,931 bits of the square root of e", so now that has very low Kolmogorov complexity. Because of this, it's very unlikely that anyone has sat down and figured out the exact Kolmogorov complexity of some nontrivial string with respect to some specific Turing machine encoding. It would be very difficult to do, and nobody cares about the answer because, in a sense, it's just an artefact of the choice of Turing machine encoding. Unlike actual programming languages, there isn't really any standard scheme of coding Turing machines as strings, so all your hard work would just be proving an uninteresting fact about your arbitrary choice of coding.
> 3 votes

---
Tags: information-theory, kolmogorov-complexity, descriptive-complexity
---


# Question
Title: Questions about Randomized Median algorithm?
In textbook by Mitzenmacher and Upfal here, they write in page 62, the following:

> By repeating Algorithm 3.1 until it succeeds in finding the median, we can obtain an iterative algorithm that never fails but has a random running time.

Note that that the algorithm has linear running time. Now, if we repeat this algorithm for k times, then the running time would be O(kn). Now, how they say that "By repeating algorithm until it succeeds in finding the median, we can obtain an iterative algorithm"? I do not understand how they get an iterative algorithm. In order to get an iterative algorithm, then the algorithm must call itself and must have a logarithmic running time.

Another question: What does they mean by "it has a random running time"?

About iterated algorithm, please look here. To see the algorithm, look at the book in page 59.

# Answer
> 3 votes
Let's start with your second question. A *random running time* is a running time which is a random variables. As a simple example, consider an algorithm which tosses a fair coin until it come up heads. The running time is a random variable whose distribution is, roughly speaking, geometric. This is not so different from the randomized median algorithm: every run of the median algorithm is like a coin toss, and you iterate running it until it comes up "heads" (succeeds).

Now, for the name *iterative algorithm*. Here is the algorithm you describe:

```
repeat
  run Algorithm 3.1
until the algorithm succeeds

```

This is the epitome of iteration – the algorithm consists of a single loop.

You write

> In order to get an iterative algorithm, then the algorithm must call itself and must have a logarithmic running time.

I'm not really sure why you think that an iterative algorithm should call itself. Indeed, algorithms calling themselves are usually known as *recursive algorithms*. (As an aside, an iteration of the form considered here is a special case of recursion known as tail recursion.)

Also, I'm not really sure why the algorithm should have a logarithmic running time. The standard algorithm for summing an array is iterative and runs in linear time.

---
Tags: algorithms, randomized-algorithms, randomized
---


# Question
Title: Printing words starting with a given letter with the least amount of appearances with the print itself being an another appearance
I've had problems with this one and was unable to solve it on my Algorithms 1 exam:

Input: -n words -k letters

Problem: For each letter print out the one word which starts with that letter and has the least number of appearances. If there are more than one, write the lexicographically smallest one. The printing of a word counts as an appearance.

Complexity: Time: O (nlogn + k) Space: O ( n + k )

This is the first algorithm I am unable to solve in given time complexity and it is driving me crazy.

Appreciate the help!

Example:

n=6 words: dog bark dog woof doggy doggy

k=2 letters and corresponding outputs: d - 2 is the least number of appearances of a word starting with d , dog and doggy - dog is the lexicographically smaller one so we print dog

if we say d again, since we printed out dog, that counts as another appearance so the only word appearing twice is doggy, and we print that one

# Answer
> 0 votes
The following assumes that you can store words in $O(1)$ space and compare them in $O(1)$ time.

For each letter $\ell$ keep:

* The number of appearances $n\_\ell$ of the word starting with $\ell$ that appears the least amount of times.
* A list $L\_\ell$ of words starting with $\ell$ that appeared $n\_\ell$ times, in lexicographic order.
* A list $R\_\ell$ of words starting with $\ell$ that appeared $n\_\ell + 1$ times and are smaller than the first word in $L\_\ell$, in lexicographic order.
* A sorted list $S\_\ell$ of pairs $(n\_w, w)$, where $w$ is a word starting with $\ell$ that appears $n\_w \ge n\_\ell+1$ times and is not in $R\_\ell$. The pairs are sorted in lexicographic order.

Notice that you can construct everything above in $O(n \log n)$ overall time *for all the letters $\ell$*.

When you have to return a word starting with letter $\ell$, do the following:

1. Remove the first word $w^\*$ from $L\_\ell$ and output it.
2. Insert $w^\*$ into $R\_\ell$.
3. Insert all the words $w$ from a pair $(n\_w, w)$ of $S\_\ell$ such that (i) $n\_w = n\_\ell + 1$, and (ii) $w$ precedes the smallest word of $L\_\ell$, into $R\_\ell$. Delete the corresponding pairs from $S\_\ell$. Notice that these are always the first elements in $S\_\ell$. If $L\_\ell$ is empty, then ignore constraint (ii).
4. If $L\_\ell$ is empty, increase $n\_\ell$ by 1, swap $R\_\ell$ and $L\_\ell$, and repeat step 3.

Steps 1, 2, and 4 can be performed in constant time. Step 3 requires a constant amount of time, plus a time proportional to the number of words $w$ moved from $S\_\ell$ into $R\_\ell$. This second term is upper bounded by $O(n)$ *across all letters* as this is an upper bound on the number of pairs contained in all $S\_\ell$.

---
Tags: algorithms
---


title: Complexity of Double Selection Sort

text:
# Question
Title: Complexity of Double Selection Sort
I would like to find the best, average, worst-case complexities of below code.

Its a variant of selection sort. In each pass both min and max is calculated and placed at proper position

```
def double_selection_sort(arr):
    n = len(arr)
    for i in range(int(n/2)):
        _min, _max = i, n-i-1
        for j in range(i+1, n-i-1):
            if arr[_min] > arr[j]:
                _min = j
            if arr[_max] < arr[j]:
                _max = j
        arr[i], arr[_min] = arr[_min], arr[i]
        arr[n-i-1], arr[_max] = arr[_max], arr[n-i-1]

```

I think its in the order of O(nlogn).

Thanks in Advance

# Answer
> 1 votes
This variant decreases number of main loop passes by factor of *2*, but in return loop body uses twice workload.
Since the change is minor, you can simply read complexity from basic *selection sort*.

The selection sort has this property that number of swaps is at most $n$, finding element to its proper place, so it takes $\mathcal O(n)$ swaps in the worst case. There is no mechanism to ignore swaps or detect sortedness, two loops are passing through every element, so we can simply infer that best case is equal worst case and equal average case.
Two nested loops with arithmetic progression (array elements to be viewed decrease by one each step) $\sum\_{i=1}^{n-1}i = \frac{1}{2}(n^2-n)$ are now decreased, giving $\frac{1}{4}(n^2-n)$, so still $\mathcal O(n^2)$ for all cases.

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


# Question
Title: How to determine if this problem is decidable?
I am currently stuck on the following problem:

**Given a WHILE-program P and the knowledge that all input variales are set to 0, is it decidable if a specific instruction is reached 1000 times?**

My intuition is that it is not decidable. Rice's theorem says that a non-trivial property of a program is always undicidable. But I am not sure if "a specific instruction is reached x times" even qualifies as a "property of a program".

I am stuck on this for a while now, so I hope someone can give a hint where to look to find an answer to this problem. Thank you so much! All help is greatly apprechiated.

# Answer
As Konstantin Vladimirov said in the comment: Consider you have this program. Take any while-program and put any instruction 1000 times just before halt. Next run your program and ask if this instruction will be reached 1000 times. Bingo, halting is solved.
> 3 votes

---
Tags: computability, decision-problem, rice-theorem
---


# Question
Title: How to merge a lot of trees into one single graph?
I have a few different trees, which resemble what the AST that compilers often deal with.

For example:

tree 1

( (a, b), (c, d) )

Imagine that each tree split represents the function "add", then tree 1 simply says: add a and b, then add c and d, in the end, add the sum of these 2 sums as the final result.

tree 2

( ( (a, b), (c, d) ), (e, f) )

obviously, I can merge tree 1 into tree 2, because tree 2 is simply constructed by adding a sibling (e, f) to tree 1.

By doing so, I don't need to re-visit a, b, c , d twice, I can simply add e and f, and add the result to the result of tree 1, to get the result of tree 2.

If I have a lot of these kind of trees, with overlapping (redundant sub-subtrees), is there an algorithm that can automatically create a graph that covers all the computation in the most efficient way ?

PS: all the trees share the same set of leaf,in this case, a b c d e f. Some trees are taller (deeper), some are shallower.

PS2: tree are not necessarily binary trees. A tree could have multiple

PS3: there could be a tree like ( (a,b), (g,h) ), i can still be partially merged with tree 1

# Answer
> 1 votes
Yes, this is sort of common subexpression elimination.

Simple approach for binary trees: introduce nodes 1 for a ... 6 for f.

Traverse your trees. When you have new pair like (1, 2) or (4, 5) introduce for them new nodes like 7 and 8, when you hit old pair, add edge from it.

You will need unordered map from pair of nodes to node, representing this pair:

```
(1, 2) -> 7
(3, 4) -> 8
(7, 8) -> 9
etc...

```

More on CSE avaliable by following links from wikipedia

If tree is not binary tree, first make it binary tree with first child / right sibling procedure. CSE in compilers most often is done on three-address code (like GIMPLE in GCC), i.e. on binary expressions only just because it is really more convenient

---
Tags: graphs, trees, graph-traversal, search-trees
---


# Question
Title: How to prove the union of languages recognized by a set of turing-recognizable Turing machines is also turing-recognizable?
Let $G = \\{\langle M\_1\rangle, \langle M\_2\rangle, \langle M\_3\rangle,\cdots\\}$ be an infinite turing recognizable language, whose members are descriptions of turing machines.

How can one prove that the union of all the languages recognized by the turing machines in $G$, $L(M\_1) \cup L(M\_2) \cup L(M\_3)\cup\cdots $ is turing recognizable?

I tried to prove it by building an enumerator for the language, using the fact that since $G$ is turing recognizable it can be produced by one.

```
E' =
1. Initialize steps counter i=0
2. Run E, the enumerator of G, number of steps equal to i.
3. For every turing machine description M produced by E:
   3.1 for every input word corresponding to 0 up to i according to lexicographic order do:
      3.1.1 Run M on the current input.
      3.1.2 print if M accepts.
4. increase i by 1, and go back to step 2.

```

Is this a correct approach? Running the enumerator for a limited amount of steps would produce the same words over and over again. Is this not a problem when creating an enumerator? Is $E'$ valid and producing the language as needed? If not, what should be changed?

# Answer
Your enumerator is incorrect. Because there are infinitely many Turing machine descriptions in $G$, the loop corresponding to Line 3 will not halt, so `i` will never be increased. Also, Line 3.2 may not halt too.

The correct enumerator is:

```
E' =
for i = 1 to infinity:
    Run E, the enumerator of G, to get the ith description of Turing machine <Mi>
    Build an enumerator Ei for Mi
    for j = 1 to i - 1:
        Run Ej to get the ith string, print it
    Run Ei to get the first i strings, print them

```

Suppose $E\_i$ prints $s\_{i1},s\_{i2},\ldots$ in order. Then after $i$ iterations, $E'$ would have printed $s\_{11},\ldots,s\_{1i},s\_{21},\ldots,s\_{2i},\ldots,s\_{i1},\ldots,s\_{ii}$ (note this is not the order they are printed), and would print $s\_{1(i+1)},s\_{2(i+1)},\ldots,s\_{i(i+1)},s\_{(i+1)1},\ldots,s\_{(i+1)(i+1)}$ in order in the $(i+1)$th iteration. Of course, before printing a string, you can check if it has been printed to avoid duplicates.
> 0 votes

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


title: Poly-time reduction from ILP to SAT?

text:
# Question
Title: Poly-time reduction from ILP to SAT?
So, as is known, ILP's 0-1 decision problem is NP-complete. Showing it's in NP is easy, and the original reduction was from SAT; since then, many other NP-Complete problems have been shown to have ILP formulations (which function as reductions from those problems to ILP), because ILP is very usefully general.

Reductions **from** ILP seem much harder to either do myself or track down.

Thus, my question is, does anyone know a poly-time reduction from ILP to SAT, that is, demonstrating how to solve any 0-1 ILP decision problem using SAT?

# Answer
0-1 ILP formulated as:

Does there exist a vector $\mathbf{x}$, subject to constraints:

$$ \left.\begin{array}{rrrrr|rr} a\_{11} x\_1 & + &a\_{12} x\_2 & ... + & a\_{1n} x\_n\le b\_1 \\ a\_{21} x\_1 & + &a\_{22} x\_2 & ... + & a\_{2n} x\_n\le b\_2 \\ ...\\ a\_{m1} x\_1 & + &a\_{m2} x\_2 & ... + & a\_{mn} x\_n\le b\_m \\ \end{array}\right. $$

Domain of x: $\forall\_{x\_j \in \mathbf{x}} x\_j\in \\{0,1\\}$

## Reduction to k-sat:

First reduce to circuit sat:

1. Start with the first row, create a boolean variable for representing each bit in $a\_{1j}$ and one boolean variable for $x\_j$. Then make variable for $b\_1$. Make an addition circuit (pick your favorite) adding the row up.
2. Then make a comparison circuit, declaring the sum to less than $b\_1$ (with a lightbulb that lights up if they are).
3. Convert these two circuits to CNF, filling in the $a\_{1j}$ variables and $b\_1$ since they are given.
4. Repeat for all rows, but reuse the $x\_j$ variables between them.
5. Take all the comparison bulbs and AND them together to get a single lightbulb as output. The SAT problem would now be "what inputs for all $x\_j$ will make this final ANDed lightbulb light up"

The final CNF will contain all the constraints.
> 14 votes

# Answer
It is some sort of necro-answer to already answered and accepted question, but I want to note, that there is really easier way.

Consider you have one of inequalities like this:

$5\*x\_1 + 2\*x\_2 + 3\*x\_3 \leq 6$

You may easily test all no-vectors for this inequality: $(1, 1, 1)$, $(1, 1, 0)$ and $(1, 0, 1)$ others are ok.

First vector $(1, 1, 1)$ means that all three can not be true: $\neg(x\_1 \land x\_2 \land x\_3)$ and we may rewrite this as a disjunct $(\neg x\_1 \lor \neg x\_2 \lor \neg x\_3)$.

This way you may form 3 clauses from no-vectors: $(\neg x\_1 \lor \neg x\_2 \lor \neg x\_3)$, $(\neg x\_1 \lor \neg x\_2 \lor x\_3)$ and $(\neg x\_1 \lor x\_2 \lor \neg x\_3)$

Traversing all inequalities and collecting clauses you will get cnf in the end. Often this cnf will be WAY SIMPLER, then one, that results from accepted answer. Cost is harder pre-processing, though.
> 4 votes

---
Tags: np-complete, reductions, satisfiability, integer-programming
---


# Question
Title: How to show that the product of two binary numbers can be determined in AC1?
I was working on a proof to determine that a product cannot be done in AC0, how can a proof that can be done in AC1?

# Answer
Multiplication can be done even with stronger restrictions, like $AC^1$ with bounded fan-in.

Proof is little hard to typeset here, but I will outline the sketch and give a link.

1. You shall prove, that addition of two m-bit numbers have $O(m)$ size and constant depth circuit and thus is in $AC^0$. This is pretty simple (start with looking for $O(m)$ depth and then simplify)
2. Then you need to generalize this result to addition of many m-bit numbers and show that it have logarithmic depth and thus in $AC^1$
3. And finally what you are looking for (product in $AC^1$) is simple corollary

Look into those lecture notes for example, where this proof is done in great details.
> 2 votes

---
Tags: complexity-theory, circuits
---


# Question
Title: Propositional truncation of excluded middle
It is clear to me that it should be impossible to prove :

```
exclMidl = isProp A → ((A) ⊎ (¬ A))

```

Because it would give deciding oracle for every Proposition.

My question is about the following Types:

```
exclMidl' = isProp A → ∥ ((A) ⊎ (¬ A)) ∥

```

or

```
exclMidl'' = isProp A → ∥ ((A ≡ Unit) ⊎ (A ≡ Empty)) ∥

```

Are they provable in cubical Agda? What HoTT can say about them?

Those types would only state that propositions are either True or False but would hide information about actual Truthness of A, preventing us from constructing universal oracle, but allowing, for example, to do a proof for both cases even for undecidable propositions.

Is my intuition about such types correct?

# Answer
The only way to prove ∥ X ∥ is to prove X (unless you admit some other axiom). So, assuming P is a proposition, there is no way to prove ∥ ((A) ⊎ (¬ A)) ∥ if you cannot prove ((A) ⊎ (¬ A)).

It is not a correct intuition that undecidable propositions are either true or false, just we do not know about it.

A formal system S with an undecidable proposition P can always be extended either in S'=(S,p:P), or S''=(S,p:¬ P) where p is taken as a new axiom. Both S' and S'' are then consistent formal systems, provided S is. If P were already true or false in S, then either S' or S'' would be inconsistent.

A formal system is meant to be interpreted, and can usually be interpreted in different ways. Undecidable propositions in a formal system are propositions that can be true in some interpretations, and false in other interpretations. A proposition is said to be true (resp. false) *within a formal system* when it is true (resp. false) in *all* possible interpretations. So there are lots of propositions that are neither true nor false *within* the formal system.

The confusion comes from the different meanings for 'true': the truth *within* the formal system usually does not match exactly the truth in the *interpretation* (or intuition) that you have in mind when you are working with the formal system...
> 3 votes

# Answer
Another thing you should know is that those truncations don't hide anything. For instance, it is relatively simple to prove the lemma:

$$\mathsf{isProp}\ A → \mathsf{isProp}\ (A \uplus ¬ A)$$

which means that we can extract the evidence from $\\| A \uplus ¬A \\|$. I think the same is true of the $A \equiv \mathsf{Unit}$ version, because all types involved are easily shown to be in:

$$\mathsf{HProp} = Σ\_{A : \mathsf{Type}}\ \mathsf{isProp}\ A$$

which is itself a set, and thus its paths are propositions. So your two latter formulations allow deriving the first.

I don't think you should think of the propositional truncation as 'freeing' you from needing (positive) computataional evidence for things, or covering up the fact that you don't have any. In fact, that is one of the things that makes truncation rather different from double negation (which also turns things into propositions). Truncation is still constructive, and if you add non-constructive axioms that result in truncated things, you are in general still making the logic non-constructive.
> 1 votes

---
Tags: dependent-types, homotopy-type-theory, agda, cubical-type-theory
---


# Question
Title: Normal colorings of cubic graphs (part 1)
> **Edit 2019 June 27** Question 3 is new

...

> **Definition** A normal $k$-coloring of a cubic graph (3-regular graph) is a proper coloring of the edges with $k$ colors such that each edge an its adjacent edges are colored with either five colors, or with three.

There is also the following

> **Conjecture** Every bridgeless cubic graph (that is, a cubic graph without a cut edge) can be normally 5-colored.

We are looking for algorithms to normally color cubic graphs

> **Questions**
>
> 1. Could you suggest an algorithm to find normal $k$-colorings of cubic graphs, with $k$ at most 9, that is efficient and simple. The coloring should include at least one edge $e$ such that the $e$ and its adjacent edges are colored with 3 colors, if this is possible. It is known that 9 colors should suffice. It is my understanding that a linear time algorithm is known, but I've not been able to find it in the literature.
>
> More importantly:
>
> 2. Could you suggest an algorithm to find normal 5-colorings of cubic graphs if they exist?
> 3. Can you find a way to color the graph using a vertex coloring algorithm ... to illustrate what I mean, to do edge coloring of a graph $G$, you perform vertex coloring on the line graph of $G$. To do strong edge coloring of $G$, you perform vertex coloring on the square graph of the line graph of $G$. In that same spirit, is there a reasonable auxiliary graph on which to do standard vertex coloring to achieve a normal coloring of $G$?

If there is a better site where this question could be posted, please indicate this. If this site is not for questions requesting information about algorithms, please notify and it will be removed immediately. I have never posted in this site.

# Answer
Some old results by Vladimir Müller, On colorings of graphs without short cycles, Discrete Math. 26 (1979) 165-176, imply that Question 3 has an affirmative answer. Although the auxiliary graph is not assured to be in some way as elegant or natural as in the case of line graphs or their squares. The easiest example that I can come up with has 13 times the order of the line graph. This construction also gives an affirmative answer to Question 2.
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: Approximation algorithm to visit all nodes in an undirected, weighted, complete graph, with shortest sum of edge weights
I'm looking for an algorithm that gives a smallest value of 'travel cost' within the following constraints:

* a complete, connected, weighted graph,
* vertices are defined in 3d euclidean space,
* relatively low number of vertices (less than 500)
* no limits on how many times a node may be visited
* a fixed starting vertex
* no requirement for which vertex to end at.

I've looked at *minimum spanning tree* algorithms, but those could create sub-optimal result, because they optimize for lowest summed edge weight.

I'm suspecting this may be a variant of the traveling salesman problem and thus NP-hard. For our use case however, a good approximation will be good enough.

# Answer
Suppose $G$ is a weighted graph, and $T\_{OPT}$ is the optimal route you seek.

For clarity: $T\_{OPT}$ is a path that connects all vertices, such that for any other path $P$ that connects all vertices, it holds that $w(T\_{OPT}) \leq w(P)$.

Denote $M$ for the MST of $G$. Since $T\_{OPT}$ is a subgraph of $G$ that connects all its vertices, we can say:

1. $w(M) \leq w(T\_{OPT})$ \- by definition of MST.

Denote $M^\*$ An euler tour of $M$. Since $M^\*$ visits each *edge* of $M$ exactly twice, it holds that:

2. $w(M^\*) = 2w(M)$
3. $M^\*$ is some path that visits all vertices of $G$, hence a path that solves your problem (although we **cannot** say $w(M^\*) = w(T\_{OPT})$)

Following from 1. 2. and 3. we get:

$$w(M) \leq w(T\_{OPT})$$ $$2w(M) \leq 2w(T\_{OPT})$$ And, since $w(M^\*) = 2w(M)$ $$w(M^\*) \leq 2w(T\_{OPT})$$
> 1 votes

---
Tags: traveling-salesman, minimum-spanning-tree, euclidean-distance
---


# Question
Title: Is a language whose Turing Machine doesn't halt for some positive cases but for others does not recursive?
Say language $L$ is ***recursively enumerable***, but ***not recursive***. Say $a$ and $b$ are symbols of the alphabet and $w$ a word. Say we have the following language:

$L' = \\{ aw | w \in L \\} \cup \\{ bw | w \notin L \\}$

That is, $L'$ consists of the words that are in $L$ with an $a$ added at the beginning and the words that are not in $L$ with a $b$ at the beginning.

Is $L'$ ***not recursive***? If we had a Turing Machine $TM$ for $L'$, $TM$ would halt for some positive cases ($w \in L$) but for other positive cases ($w \notin L$) it wouldn't halt. Is it therefore not recursive and recursively enumerable?

From what I understand:

* ***Recursively enumerable:*** the Turing Machine will always halt if $w \in L$, otherwise it may or not halt.
* ***Recursive:*** it always halts.
* ***Recursively enumerable, but not recursive:*** it only halts if $w \in L$; otherwise it loops.
* ***Not recursively enumerable:*** no Turing Machine exists.

So I don't know how to classify a language whose Turing Machine halts for some of its words.

EDIT: of course, now that I think about it, if the $TM$ doesn't halt and accept for some words then they didn't belong to the language in the first place.

# Answer
> 3 votes
There are two important misunderstandings in your question.

* You talk about "the Turing machine" for a language but there isn't just one: in fact, if a language is recursive (or RE) then there are infinitely many Turing machines that decide (or accept) it.
* If a Turing machine decides a language $L$ then, by definition, it accepts every input in $L$ and rejects every input not in $L$ and, therefore, it halts on every input. It doesn't make sense to talk about a Turing machine deciding a language but not halting on some input, or not accepting some string that's in the language.

With that in mind, a language $L$ is:

* **Recursively enumerable** if there is a Turing machine that accepts every string in $L$ and does not accept any string not in $L$. It may loop or reject strings not in $L$.
* **Recursive** if there is a Turing machine that accepts every string in $L$ and rejects every string not in $L$.
* **Recursively enumerable but not recursive** if there is a Turing machine that accepts every string in $L$ and does not accept any string not in $L$, but no TM that accepts everything in $L$ and rejects everything not in. The "but..." part can be rephrased as "every Turing machine that accepts every string in $L$ must either also accept some string not in $L$ or must loop on some string not in $L$."
* **Not recursively enumerable** if every Turing machine either accepts at least one string not in $L$, or loops or rejects at least one string in $L$.

For your specific language, I'm going to assume that $\Sigma=\\{a,b\\}$. If not, then the notation gets a little uglier but nothing fundamental changes.

If $L$ is RE but not recursive, then $$L' =\\{aw\mid w\in L\\} \cup \\{bw\mid w\notin L\\}$$ is not RE. suppose it is RE and is accepted by some Turing machine $M$. Then we can decide if $w\in L$ by simulating $M(aw)$ and $M(bw)$ in parallel until one of them accepts. If $M$ accepts $aw$, then $w\in L$; if it accepts $bw$, then $w\notin L$, and one of these two things must happen. This contradicts the assumption that $L$ is not recursive.

# Answer
> 0 votes
Turing machines can halt or not halt. Languages cannot. The category of halting does not apply to them.

We say that a language is *recursive* if there is a Turing machine which always halts, and accepts exactly the words in the language. It is not the language itself which always halts, but rather the Turing machine that decides it.

In your case, the language $L'$ is not recursive, since $L$ reduces to it. More explicitly, if $L'$ were recursive then you could decide $L$: given an input $w$, run the decider for $L'$ on the word $aw$, and output the result. Since $L$ is not recursive, the only conclusion is that $L'$ also isn't.

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


title: True Error of a binary classifier

text:
# Question
Title: True Error of a binary classifier
For a given classifier h, How is the true error over a distribution D defined? \begin{align\*} L\_D(h) &= \sideset{\mathbb{E}}{}{}\_{x,y \sim D} \Pr\[h(x) \neq y\] \\ &= \sideset{\mathbb{E}}{}{}\_{x,y \sim D} \begin{cases} \Pr\[y \neq 0|x\] & \text{if } h(x) = 0, \\ \Pr\[y \neq 1|x\] & \text{if } h(x) = 1. \end{cases} \end{align\*}

I saw these two formulae here Showing that Bayes classifier is optimal Are these two equivalent?

# Answer
> 0 votes
The first line should read $$ \Pr\_{x,y \sim D}\[h(x) \neq y\]. $$ (This is assuming that the classifier is deterministic.)

We can sample $x,y \sim D$ in two steps: first sample $x \sim D'$, and then sample $y \sim C\_x$, where $C\_x$ is a distribution depending on $x$.

The second line expresses the idea $$ \operatorname\*{\mathbb{E}}\_{x \sim D'} \Pr\_{y \sim C\_x}\[y \neq h(x)\] $$ in an elaborate way.

Both of these are the same, and equal to $$ \operatorname\*{\mathbb{E}}\_{x \sim D'} \operatorname\*{\mathbb{E}}\_{y \sim C\_x} 1\_{h(x) \neq y}. $$

---
Tags: machine-learning
---


# Question
Title: Difference between multi-tape Turing machine and single tape machine
A beginner's question about "fine-grained" computational power.
Let $M\_k$ be a $k$-tapes turing machine, and let $M$ be a single tape turing machine. We know that $M\_k$ and $M$ both have the same "computable power". In addition, one can simulate $M\_k$ on $M$ in a way that every computation which takes $O(t(n))$ on $M\_k$ will take $O(t(n) \log(t(n))$ on $M$.
Here is my question:
Is there a language $L$ such that $L$ can be decided in $O(n)$ time in $k$-tape Turing machine (for fixed $k$, say 2), but can't be decided in $O(n)$ time in a single tape machine? (every single tape machine which decides $L$ needs $\Omega(n \log n)$ time).
In addition, are there any examples of two computational models (classical, not the quantum model) with the same computable power, but with fine-grained differences in their running time? (I guess that major changes in running time would contradict the extended Church-Turing thesis, which is less likely).

# Answer
The language of all palindromes needs quadratic time on a single-tape Turing machine. See for example lecture notes of Eric Ruppert. The proof uses crossing sequences. In contrast, on a two-tape Turing machine, the language can be decided in linear time.
> 3 votes

---
Tags: complexity-theory, computability, time-complexity, computation-models
---